YifanChen's Blog

一个专注技术的新手程序员

0%

技术栈

  • Frontend: React
  • Server-side Rendering: Next.js
  • Styling: Tailwind CSS
  • Data abstraction layer: Prisma
  • Storage: MongoDB
  • Authentication: NextAuth
  • Deploy: Vercel
  • Typescript
  • the entire website fully

The entire website fully responsive across all devices.

实现的功能

  • credential login: username + password
  • profile: automatically generated once we register
  • homepage: loaded with a random movie-billboard
  • movies: load from database
  • favourites: add movies as favourites
  • botton: shows more information about the movie
  • play the movie
  • Google and GitHub oauth login

精简笔记与全栈开发的一般流程

登录页面

先在pages中创建auth.tsx,然后在components中创建Input.tsx,将其加入到auth.tsx中。实现next auth时需要创建pages/api/[…nextauth].ts文件。

通过授权登录保护登录界面以外的路径

保护路由:

  • serverAuth.ts(lib):利用 next-auth 的 getSession 实现API路由的用户登录检查,防止未登录用户访问。
  • current.ts(pages/api):API路由,使用 serverAuth.ts 验证用户登录,返回用户信息或错误。

前端用户信息获取:

  • fetcher.ts(lib):通过 axios 封装的简易数据获取函数。
  • useCurrentUser.ts(hooks):自定义Hook,结合 swr 和 fetcher.ts 从 /api/current 获取当前登录用户信息。

客户端路由保护与个人资料页面:

  • index.tsx 和 profiles.tsx(pages):通过 getServerSideProps 中的 getSession 实现路由保护,控制访问权限。
  • 页面重定向:auth.tsx 调整登录后重定向逻辑,确保正确导向 /profiles。

实现细节:

  • 用户状态展示:在 profiles.tsx 中展示用户信息,并实现点击默认头像返回首页的功能。
  • 环境配置调整:通过修改 .env 和 package.json 解决开发中遇到的端口配置问题,保证登录流程正常。

导航组件

在这个项目中,开发了一个导航组件(Navigation Component),涉及了几个主要的文件和它们之间的关系,以及各自的功能和作用:

  1. index.tsx(主页文件):这是应用的入口页面,最初被清理以只保留基本结构。它通过 getServerSideProps 功能检查用户的会话,基于会话存在与否决定重定向到登录页面或显示主内容。后续,Navbar 组件被引入到此文件中,作为页面的一部分。

  2. Navbar.tsx(导航栏组件):位于 components 文件夹内,Navbar 是顶部的导航条组件,负责显示应用的导航链接。它包括了一个动态背景变化的功能,随着页面滚动,背景从透明变为不透明。

  3. NavbarItem.tsx(导航项组件):同样位于 components 文件夹内,用于表示 Navbar 中的单个导航链接。它通过 props 接收 label 来显示不同的导航项。

  4. MobileMenu.tsx(移动菜单组件):这个组件负责在小屏幕上显示一个可展开的移动菜单。它通过 visible prop 控制显示状态,包含多个 NavbarItem 组件来展示导航选项。

  5. AccountMenu.tsx(账户菜单组件):用于在 Navbar 组件中显示用户的账户菜单,它提供了注销功能并可以通过 visible prop 控制其显示。

项目中还实现了一些额外的交互特性,比如:

  • 使用 React 的 useState 和 useEffect Hooks 来管理组件的状态和生命周期,例如控制菜单的显示状态和根据页面滚动动态改变导航栏背景。
  • 通过 useCallback 来优化事件处理函数,避免不必要的重新渲染。
  • 导航组件和移动菜单的显示逻辑,包括在小屏幕上通过点击“浏览”来展开和隐藏导航项。
  • 在 Navbar 组件中,引入了 react-icons 库中的图标来增强视觉效果,并通过条件渲染实现了箭头图标的旋转动画,以指示菜单的展开和收起状态。

整体而言,这个导航组件通过组合多个子组件和利用 React 的特性,实现了一个响应式、具有交互性的用户界面,能够适应不同的设备和屏幕尺寸。

广告牌组件

首先将定义有电影信息的json文件手动添加到MongoDB中。
然后创建新的api:random,用于随机返回一部电影。
hooks/useBillboard.ts中写代码以避免对首页推荐电影的重复加载。在components中新建Billboard.tsx,然后在index.tsx中引入Billboard
接着在Billboard.tsx中填入具体的内容,目的是fetch the data for a random movie,并继续加入电影、电影名、电影介绍和More info按钮。

电影列表和电影卡片组件

定义api: pages/api/movies/index.ts,加载所有电影。
接着在hooks文件夹中创建useMovieList.ts,用于返回api/movies中得到的数据。
接着在components中创建MovieList.tsx,并在pages/index.tsx中装入MovieList并传入必要的参数,并使用上面定义的hook: useMovieList.ts
接着在components文件夹中创建MovieCard.tsx文件,用于实现电影卡片组件,并将MovieCard放入MovieList.tsx中。

收藏功能

定义api: pages/api/favorite.ts,用于实现用户在收藏和取消收藏电影时对数据库的操作。
再定义一个api: pages/api/favorites.ts,用于加载我们收藏的电影列表。
接着写一个hook: useFavorites.ts,用于调用第二个api从而加载我们收藏的电影列表。
再写一个组件components/FavoriteButton.tsx,作为收藏按钮。
将该按钮加入MovieCard中。然后在Trending Now列表以外再创建一个My Favorites列表,这是在pages/index.tsx中实现的。
最后让favorite按钮变得可交互。这样在Trending Now列表上的电影上的加号时,其就会被添加到My List,然后加号会变成勾。这样一部电影就被收藏了。取消收藏也是同理。

电影播放功能

首先定义api: 创建pages/api/movies/[movieId].ts,用于通过外部传入的movieId找到电影。
再创建hooks/useMovie.ts,调用上述api,并负责给上述api传入参数movieId。
接着写播放按钮:components/PlayButton.tsx,并在components/Billboard.tsx中加入播放按钮。
现在实现了点击播放按钮,跳转到另一个页面的功能,接着在MovieCard组件中也实现这个功能。
然后具体写跳转到的/watch页面,创建pages/watch/[movieId].tsx,并在这个页面中实现加载视频名字、返回等功能。

电影详细信息功能

实现的功能:点击More Info按钮,会显示电影的信息。
创建用于状态管理(打开或关闭More Info)的钩子:hooks/useInfoModel.ts
创建显示电影详细信息的组件:components/InfoModal.tsx
在pages/index.tsx中加入上述组件。
给InfoModal组件加上关闭、播放、收藏按钮,最后加上电影信息等字样。
利用onClick函数实现点击关闭按钮关闭页面的功能。
pages/index.tsx中实现对组件InfoModal.tsx的触发,从而展现电影的详细信息。
components/Billboard.tsx中实现点击More Info按钮触发组件InfoModal.tsx,从而展现电影的详细信息。
在电影卡片组件中同样实现点击按钮展现电影详细信息。
修复个人profile中名字始终加载为username的问题。

给全栈项目开发新功能的一般过程

熟悉了上述精简版本的笔记后,我们可以对全栈项目(react + next.js)的开发做一些总结。

对于实现登录页面和通过授权登录保护登录界面以外的路径,这两项属于偏后端的范畴,主要利用的是next.js的一些特性(特别是pages和api)。这两个任务没有什么一般性的套路,需要用到的文件夹也比较复杂,包括pages, hooks, lib等,跟着讲义一步步实现。

对于实现导航组件,这个属于偏前端的范畴,主要需要在pages中定义一个菜单界面,再在components中定义若干个组件。在这里需要注意组件的复用。组件拼凑组合起来就能实现一个网页。同时还需要注意如何实现交互特性和其他的一些细节。

对于广告牌组件、电影列表和电影卡片组件、收藏功能、电影播放功能、电影详细信息功能,这些都属于前后端交互的范畴,是有统一的开发套路的。一般来说是先定义api,再定义hook(调用api),再定义组件(调用hook获取api的数据),再将组件加入到页面(pages)中。这就是开发全栈项目的一般的新功能(非拓荒)的一般过程。

我的思考

  1. Tailwind CSS的好处:我的主要感受是不需要手写css文件,直接在classname中写内容就可以。注意使用Tailwind CSS前,需要进行必要的配置。Tailwind CSS的具体优点如下所示:

    • 快速原型开发
      Tailwind 的实用工具类使得快速原型设计变得非常简单。你可以通过组合不同的类来快速构建界面,而不需要离开 HTML 文件去编写和调试 CSS 文件,这可以显著加快开发速度。

    • 一致性和可重用性
      通过使用 Tailwind 提供的实用工具类,可以在整个项目中保持样式的一致性。由于你在不同的地方复用相同的实用工具类,这自然而然地导致了样式的可重用性和一致性。

    • 可定制和可配置
      Tailwind CSS 高度可定制。你可以根据项目的设计指南调整配置文件(如颜色、字体大小、边距等),这使得创建符合品牌指南的设计变得简单。

    • 减少 CSS 的复杂性
      由于采用实用工具类的方式,你可以避免编写过多的自定义 CSS 和处理复杂的 CSS 继承关系,这降低了代码的复杂性。

    • 响应式设计友好
      Tailwind CSS 内置了响应式设计的支持,通过简单的前缀可以轻松地实现不同屏幕尺寸的样式适配,而不需要编写额外的媒体查询。

    • 减少未使用的 CSS
      通过与 PurgeCSS 的集成,Tailwind CSS 可以在构建过程中自动移除未使用的 CSS,这意味着最终的样式表非常精简,加载时间快。

    • 总结
      尽管 Tailwind CSS 提供了诸多好处,如加速开发、提高一致性和可维护性,但它也有一定的学习曲线,尤其是对于习惯了传统 CSS 开发方式的开发者来说。此外,一些开发者可能会对在 HTML 中大量使用实用工具类表示担忧,担心这会导致 HTML 文件的可读性降低。不过,对于许多项目和团队而言,Tailwind CSS 提供的好处远远超过了这些潜在的缺点。

  2. Google oauth比较难用。在本地将项目跑起来时,Google oauth功能正常,但当我尝试在vercel上部署本项目时,Google oauth就完全无法正常使用,甚至每次产生的报错信息都不相同。与此形成鲜明对比的是,GitHub oauth比较好用,配置和更改都较为简单,且将项目部署在vercel上以后再使用GitHub oauth也不会出问题。

  3. Next.js和React各自的作用:

    React 和 Next.js 在一个项目中的共存实际上非常常见,并且它们各自扮演着互补的角色。理解它们的主要用途有助于更好地利用这两个库/框架来构建你的应用。

    React

    React 是一个用于构建用户界面的 JavaScript 库,由 Facebook 开发。它的主要特点是组件化开发和声明式编程,使得开发复杂、高性能的单页应用(SPA)变得简单。React 本身主要关注于视图层(UI),允许开发者以组件的形式构建复杂的用户界面。它并不提供诸如路由、服务器端渲染等功能,这些通常需要通过其他库或框架来实现。

    Next.js

    Next.js 是一个基于 Node.js 的框架,它为 React 应用提供了额外的结构和功能,如自动的代码分割、服务器端渲染(SSR)、静态站点生成(SSG)、基于文件的路由系统、API 路由等。Next.js 旨在解决 React 单页应用的一些限制,特别是在 SEO 和首屏加载性能方面。通过服务器端渲染,Next.js 可以提前渲染页面,使其内容能够被搜索引擎索引,同时也提升了页面加载的速度。

    它们是如何一起工作的

    • React 在项目中的角色:负责定义应用的组件结构、状态管理和用户交互逻辑。开发者会使用 React 来创建应用的各个界面组件。
    • Next.js 在项目中的角色:提供框架和额外功能,帮助这些 React 组件以更高效、优化的方式被呈现和服务。例如,Next.js 通过文件系统提供的路由功能,自动将位于 pages/ 目录下的 React 组件转换为可访问的页面

    总结

    在一个项目中,React 用来构建用户界面的组件,而 Next.js 则用来增强 React 应用,提供路由、预渲染(SSR 或 SSG)等功能,以及优化应用的性能和可访问性。Next.js 让开发者能够更专注于业务逻辑和组件本身,而不是底层的架构问题,从而简化了 React 应用的开发和部署过程。简言之,你可以将 React 视为构建应用的砖块,而 Next.js 则是将这些砖块组织起来,建造出结构化、高效、易于维护的应用的框架。我的理解:React只能做前端,而React+Next.js就可以做全栈了

  4. Prisma是一款现代化的ORM框架,它可以连接到多种数据库类型(如 PostgreSQL 、 MySQL 、 SQLite 和 SQL Server等),在本项目中我们用Prisma连接了MongoDB。在ORM的帮助下,我们不需要写SQL语句,只需要定义数据库中的数据名称和数据类型,就可以实现对数据库的各种操作。

  5. 本项目中的大多数代码都是Typescript(.ts)代码或者TypeScript JSX(.tsx)代码。前者是基于javascript开发的。TypeScript 是 JavaScript 的一个超集,这意味着它包含了 JavaScript 的所有功能,并在此基础上添加了更多的特性。后者是 TypeScript 的扩展,允许在 TypeScript 文件中使用 JSX 语法。JSX 是一种语法糖,允许开发者在 JavaScript 代码中写像HTML一样的标记语言,这在React 开发中非常常见。由于 TypeScript 默认不理解 JSX 语法,TSX(.tsx 文件扩展名)提供了一种方式来使用 TypeScript 和 JSX。因此,.tsx 文件通常用于包含 JSX 的 TypeScript 项目,尤其是在开发 React 组件时。简而言之,当代码中需要有类似HTML的代码时,即需要创建一个页面或者页面的一部分时,用tsx。无类似HTML的代码,则用ts。在本项目中,定义所有组件的components文件夹中的文件全用了tsx,因为要写HTML代码;同理,pages文件夹中除了api文件夹以外的所有文件用的也是tsx。剩下的文件夹中的文件普遍用的是ts,包括hooks文件夹,lib文件夹和pages/api文件夹。

  6. 本项目中几个主要文件夹的作用:

    属于 Next.js 的特定文件夹:

    • pages:这是 Next.js 特有的一个文件夹,用于基于文件系统的路由。在 Next.js 中,pages 目录下的每一个文件都会自动对应一个路由,这是 Next.js 框架的核心特性之一。pages中还有api文件夹,因此在本项目中可以像前后端分离的项目那样在后端定义api,然后在前端调用。只不过本项目中是在next.js实现的伪后端中定义api,然后在react实现的纯前端中调用api
    • public:这个文件夹也是 Next.js 的标准部分,用于存放静态文件,如图片、字体等。在项目中,你可以通过相对路径直接引用 public 文件夹中的资源。
    • styles:虽然存放样式的做法在前端项目中非常常见,但在 Next.js 项目中,styles 文件夹通常用于组织 CSS 或 SCSS 文件。Next.js 支持 CSS Modules 和内置的 Sass 支持,这个文件夹通常用来利用这些特性。本项目中的styles文件夹中只有一个global.css文件,主要负责对tailwind css的配置和定义一些默认的css格式。

    通常属于开发者根据项目需求创建的文件夹(既适用于 React,也适用于 Next.js):

    • components:存放 React 组件的文件夹。这些组件可以在不同的页面中复用。这是 React 项目的常见结构,但在 Next.js 项目中同样适用。

    • hooks:存放自定义 React 钩子(Hooks)。自定义钩子是 React 16.8 引入的功能,用于在函数组件之间复用状态逻辑。

    • lib:通常用于存放一些工具库或者用于与 API 交互的函数等。这个文件夹的具体用途依项目需求而定,既适用于纯 React 项目,也适用于 Next.js 项目。

    数据库相关的文件:

    prisma:这个文件夹通常用于存放与 Prisma 相关的配置和模型文件。Prisma 是一个流行的 Node.js 和 TypeScript ORM(对象关系映射),用于构建数据库访问。这不是 Next.js 或 React 特有的,而是根据你的项目是否需要与数据库交互来决定使用。

    总结:
    Next.js 特有:pages 和 public 文件夹是 Next.js 特定的,而 styles 虽然不是 Next.js 特有的,但其在 Next.js 项目中的使用方式往往利用了 Next.js 的一些特性。

    React 和 Next.js 通用:components、hooks、lib 和 prisma 文件夹是根据开发者的项目需求创建的,它们既适用于 React 项目,也适用于 Next.js 项目。这些文件夹的使用反映了现代前端项目的一些最佳实践,如组件化开发、自定义钩子的使用等。

  7. 本项目中使用到了hook的以下功能:

    • 状态管理 (useState)
      这是 Hooks 最基本的用途之一,允许在函数组件中添加状态。这对于实现按钮点击、输入表单处理、切换UI组件显示隐藏等功能至关重要。

    • 数据获取(useSWR
      useSWR 是一个由 Vercel 团队开发的 React Hook,它是 SWR (Stale-While-Revalidate) 数据获取库的一部分。SWR 是一种缓存策略,其名称来自 HTTP 缓存无效化策略,意味着“先返回缓存中的数据(陈旧的),然后发送请求(重新验证),最后用新数据替换旧数据”。useSWR 主要用于数据获取场景,特别是在需要频繁请求更新数据的应用中,它提供了一种简单而强大的方法来获取、缓存、更新远程数据。

    • 副作用处理 (useEffect)
      用于执行副作用操作,如数据获取(调用API)、订阅/取消订阅事件、直接操作DOM。这对于在组件加载、更新或卸载时执行外部操作非常有用。

    • 性能优化 (useCallback)
      useCallback 可以避免在每次渲染时都进行不必要的计算或创建新的函数实例,从而提高性能。

      需要特别注意的是,hook是一种概念,因此不局限于定义在某个特定的文件夹(如 hooks 文件夹)中,而是可以在函数的任何地方使用。在本项目中,hooks文件夹中的hooks主要负责对api的调用,而components, pages等文件夹中的hooks主要负责状态管理和性能优化。

Amazon SDE OA

  1. 题目不难,简单的算法
  2. 第二题涉及到链表的增加头、尾节点和删去头节点,但用最简单直接的做法会超时
  3. 第二题的优化做法没有完全实现(出现报错),导致第二题没有完美地做出来,应该会被拒
  4. 时间一共70分钟,乍一看很充裕,但是如果碰到要优化的地方,时间就不够用了,因此下次做OA一定要做快一些,留出充足的时间给可能需要的优化和debug。

Netflix Clone

tech stack

  • Frontend: React
  • Server-side Rendering: Next.js
  • Styling: Tailwind CSS
  • Data abstraction layer: Prisma
  • Storage: MongoDB
  • Authentication: NextAuth
  • Deploy: Vercel
  • Typescript
  • the entire website fully

The entire website fully responsive across all devices.

function overview

credential login: username + password
profile: automatically generated once we register
homepage: loaded with a random movie-billboard
movies: load from database
favourites: add movies as favourites
botton: shows more information about the movie
play the movie
Google oauth login

How to initialize next.js and Tailwind which is going to be crucial for our styling.

Environment setup

create project

terminal:

1
npx create-next-app --typescript

set everything as default

open folder netflix-clone, enter command:

1
npm run dev

The website is running on: http://localhost:1689/

clean up the project:
remove pages/_document.tsx
remove everything in pages/index.tsx except the main function:

1
2
3
4
5
6
7
export default function Home() {
return (
<>
<h1>Netflix Clone</h1>
</>
);
}

remove all the content in styles/globals.css. Get a white page with Netflix Clone.

add test.tsx in pages folder. Add the below content in test.tsx

1
2
3
4
5
6
7
const MyPage = () => {
return (
<h1>Hello New Page</h1>
)
}

export default MyPage;

I can visit Hello New Page in http://localhost:1689/test.
Delete test.tsx, it is just a demonstration of how easy it is to use Next.js.

setup tailwind

tailwind tutorial: https://tailwindcss.com/docs/guides/nextjs

run the following commands in terminal:

1
2
npm install -D tailwindcss postcss autoprefixer
npx tailwindcss init -p

Now we have tailwind.config.js and postcss.config.js. Open tailwind.config.js and write the below code (according to tailwind tutorial above):

1
2
3
4
5
6
7
8
9
10
11
12
/** @type {import('tailwindcss').Config} */
module.exports = {
content: [
"./app/**/*.{js,ts,jsx,tsx}",
"./pages/**/*.{js,ts,jsx,tsx}",
"./components/**/*.{js,ts,jsx,tsx}",
],
theme: {
extend: {},
},
plugins: [],
}

Write code in styles/globals.css to import tailwind styles:

1
2
3
@tailwind base;
@tailwind components;
@tailwind utilities;

enter the command npm run dev again and we can see a different web page, because the content in globals.css reset the css.

Try to change the color of netflix clone to green in the web page, just write the following code in index.tsx:

1
2
3
4
5
6
7
export default function Home() {
return (
<>
<h1 className="text-2xl text-green-500">Netflix Clone</h1>
</>
);
}

Auth Screen UI

In styles/globals.css, write:

1
2
3
4
5
6
7
@tailwind base;
@tailwind components;
@tailwind utilities;

body {
@apply bg-zinc-900 h-full overflow-x-hidden;
}

the web page turned to black. Add some code in globals.css:

1
2
3
4
5
6
7
#__next {
@apply h-full;
}

html {
@apply h-full;
}

create images folder in public folder and download hero.jpg and logo.png from github repository.

Create auth.tsx in pages. It is the auth page. Write the following code in it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const Auth = () => {
return (
// first div: add background pictures in auth page
// second dic: make the picture a bit darker in the large screen
// img: set logo (NETFLIX) className="h-12" makes it smaller
// third div: container
<div className="relative h-full w-full bg-[url('/images/hero.jpg')] bg-no-repeat bg-center bg-fixed bg-cover">
<div className="bg-black w-full h-full lg: bg-opacity-50">
<nav className="px-12 py-5">
<img src = "/images/logo.png" alt = "Logo" className="h-12"/>
</nav>
<div className="flex justify-center">
<div className="bg-black bg-opacity-70 px-16 py-16 self-center mt-2 lg: w-2/5 lg: max-w-md rounded-md w-full">
<h2 className="text-white text-4xl mb-8 font-semibold">
Sign in
</h2>
<div className="flex flex-col gap-4">

</div>
</div>
</div>
</div>
</div>
);
}

export default Auth;

create components folder and create Input.tsx. Write some codes in it:

1
2
3
4
5
6
7
const Input = () => {
return (
<input />
)
}

export default Input;

Now add the Input in auth.tsx :

1
2
3
4
5
import Input from "@/components/Input";

<div className="flex flex-col gap-4">
<Input />
</div>

Now add some floating labels in Input.tsx:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const Input = () => {
return (
<div className="relative">
<input
className="
block
rounded-md
px-6
pt-6
pb-1
w-full
text-md
text-white
bg-neutral-700
appearance-none
focus: outline-none
focus: ring-0
peer
"
placeholder=" "
/>
</div>
)
}

export default Input;

现在我们想在sign in之下的第一个输入框加上Email字样,当点击输入框时,Email变小,不点击输入框时,Email变大,这是一种浮动的特效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// duration-150: duration for animation
const Input = () => {
return (
<div className="relative">
<input
id = "email"
className="
block
rounded-md
px-6
pt-6
pb-1
w-full
text-md
text-white
bg-neutral-700
appearance-none
focus: outline-none
focus: ring-0
peer
"
placeholder=" "
/>
<label
className="
absolute
text-md
text-zinc-400
duration-150
transform
-translate-y-3
scale-75
top-4
z-10
origin-[0]
left-6
peer-placeholder-shown:scale-100
peer-placeholder-shown:translate-y-0
peer-focus:scale-75
peer-focus:-translate-y-3
"
htmlFor="email">
Email
</label>
</div>
)
}

export default Input;

接下来让输入框模块化。加入react的一些特性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import React from 'react';

interface InputProps {
id: string;
onChange: any;
value: string;
label: string;
type?: string;
}

// duration-150: duration for animation
const Input: React.FC<InputProps> = ({
id,
onChange,
value,
label,
type
}) => {
return (
<div className="relative">
<input
onChange={onChange}
type={type}
value={value}
id={id}
className="
block
rounded-md
px-6
pt-6
pb-1
w-full
text-md
text-white
bg-neutral-700
appearance-none
focus: outline-none
focus: ring-0
peer
"
placeholder=" "
/>
<label
className="
absolute
text-md
text-zinc-400
duration-150
transform
-translate-y-3
scale-75
top-4
z-10
origin-[0]
left-6
peer-placeholder-shown:scale-100
peer-placeholder-shown:translate-y-0
peer-focus:scale-75
peer-focus:-translate-y-3
"
htmlFor="id">
{label}
</label>
</div>
)
}

export default Input;

此时发现auth.tsx报错,在input处加入以下代码:

1
2
3
4
5
6
7
<Input
label="Email"
onChange={() => {}}
id="email"
type="email"
value=""
/>

我们发现网页上的输入框无法输入内容,在auth.tsx中加入以下代码来解决这个问题:

1
2
3
4
5
6
7
8
9
10
11
import { useState } from "react"
import Input from "@/components/Input";

const Auth = () => {
const [email, setEmail] = useState('');

label="Email"
onChange={(ev) => setEmail(ev.target.value)}
id="email"
type="email"
value={email}

现在就可以在网页端的输入框内打字了。然后将上述内容复制两次,制造出username和password的输入框。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const [name, setName] = useState('');
const [password, setPassword] = useState('');

<Input
label="Username"
onChange={(ev: any) => setName(ev.target.value)}
id="name"
value={name}
/>

<Input
label="Password"
onChange={(ev: any) => setPassword(ev.target.value)}
id="password"
type="password"
value={password}
/>

接下来写按钮login botton:

1
2
3
<button className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">
Login
</button>

产生了一个红色的按钮,点击按钮颜色会变深。

接着

1
2
3
4
5
6
<p className="text-neutral-500 mt-12">
First time using Netflix?
<span className="text-white ml-1 hover:underline cursor-pointer">
Create account
</span>
</p>

接着在login和register之间产生一个跳转。

1
2
3
4
5
6
7
8
9
const [variant, setVariant] = useState('login');

const toggleVariant = useCallback(() => {
setVariant((currentVarient) => currentVarient === 'login' ? 'register': 'login')
}, [])

<span onClick={toggleVariant} className="text-white ml-1 hover:underline cursor-pointer">
Create account
</span>

接着再将原本的login改为{variant === 'login' ? 'Sign in': 'Register'}。这样点击create account就会在sign in和register之间切换。由于在sign in时不需要看到username,而在register时要输入username,因此将username包裹在register中:

1
2
3
4
5
6
7
8
{variant === 'register' && (
<Input
label="Username"
onChange={(ev: any) => setName(ev.target.value)}
id="name"
value={name}
/>
)}

接着让按钮在sign in时显示为login,在register时显示为sign up。

1
2
3
<button className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">
{variant === 'login' ? 'Login': 'Sign up'}
</button>

接着让login界面中显示提示语:First time using Netflix. Create account。在register页面中显示提出语:Already have an account?Login.

1
2
3
4
5
6
<p className="text-neutral-500 mt-12">
{variant === 'login' ? 'First time using Netflix?' : 'Already have an account?'}
<span onClick={toggleVariant} className="text-white ml-1 hover:underline cursor-pointer">
{variant === 'login' ? 'Create account' : 'Login'}
</span>
</p>

NextAuth, Prisma, Mongo Setup

将上述登录注册的UI界面通过prisma连接到mongodb。先在vscode中安装扩展prisma,其可以帮助对prisma文件进行格式化和高亮。接着在终端输入命令:npm install -D prisma

再输入命令:npx prisma init,本命令可以产生一个schema.prisma文件。将其中的数据库修改为mongodb:

1
2
3
4
5
6
7
8
generator client {
provider = "prisma-client-js"
}

datasource db {
provider = "mongodb"
url = env("DATABASE_URL")
}

接着在终端输入:npm install @prisma/client。接着再创建新的文件夹lib。在其中创建prismadb.ts文件,写入以下代码:

1
2
3
4
5
6
7
import { PrismaClient } from '@prisma/client';

const client = global.prismadb || new PrismaClient();

if (process.env.NODE_ENV === 'production') global.prismadb = client;

export default client;

next.js具有特性:hot reloading。每次代码改变时,我们的项目自动更新并重新运行。对prisma而言,每次会产生若干个PrismaClient实例,就会得到报错:已经有若干个Prisma Client正在运行。我们将PrismaClient存储在一个全局文件中,而全局文件并不会被hot reloading影响,因此就不会产生上面的报错。接着来解决prismadb标红的错误。

根目录下创建文件global.d.ts,在其中定义prismadb,写入以下内容:

1
2
3
4
5
6
7
import { PrismaClient } from '@prisma/client';

declare global {
namespace globalThis {
var prismadb: PrismaClient
}
}

接着进入schema.prisma文件,填入DATABASE_URL。需要先进入.env文件,将其中的database url换成有效的url。在谷歌中搜索mongodb atlas,注册并登录。点击build a database。我的database的username是cyf,密码是20001017。IP地址点击add my current IP address即可。接着在overview页面点击connect,选择mongodb for vscode。复制它给出的URL并粘贴到.env文件中。需要将URL中的<password>替换为自己真实的密码。并在URL的末尾加上我的实际数据库的名字:

1
DATABASE_URL="mongodb+srv://cyf:20001017@cluster0.38xordg.mongodb.net/Cluster0"

接着,在schema.prisma文件中一次性定义好所有的models(数据模型)。因为反复修改数据模型和运行项目可能会导致一些麻烦和报错。schema.prisma文件内容如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// This is your Prisma schema file,
// learn more about it in the docs: https://pris.ly/d/prisma-schema

// Looking for ways to speed up your queries, or scale easily with your serverless or edge functions?
// Try Prisma Accelerate: https://pris.ly/cli/accelerate-init

generator client {
provider = "prisma-client-js"
}

datasource db {
provider = "mongodb"
url = env("DATABASE_URL")
}

model User {
id String @id @default(auto()) @map("_id") @db.ObjectId // 每个model都需要这一行,因为mongodb的model一定需要定义id
name String
image String? // ?表示可选,可要可不要
email String? @unique // 非必须,可能用到oauth login
emailVerified DateTime?
hashedPassword String? // 密码登录所需要
createAt DateTime @default(now())
updateAt DateTime @updatedAt // 自动更新 更新时间
favoriteIds String[] @db.ObjectId // 用户最喜欢的电影
sessions Session[]
accounts Account[]
}

// 用于Google Account或者GitHub Account
model Account {
id String @id @default(auto()) @map("_id") @db.ObjectId
userId String @db.ObjectId // account和userid之间的关系
type String
provider String
providerAccountId String
refresh_token String? @db.String
access_token String? @db.String
expires_at Int?
token_type String?
scope String?
id_token String? @db.String
session_state String?

// 将account model和user model之间通过userId连接, onDelate表示二者的删除是同步的(user被删除了,account也被删除)
user User @relation(fields: [userId], references: [id], onDelete: Cascade)

@@unique([provider, providerAccountId]) // 独一无二,不允许重复
}

model Session {
id String @id @default(auto()) @map("_id") @db.ObjectId
sessionToken String @unique
userId String @db.ObjectId
expires DateTime

user User @relation(fields: [userId], references: [id], onDelete: Cascade)
}

model VerificationToken {
id String @id @default(auto()) @map("_id") @db.ObjectId
identifier String
token String @unique
expires DateTime

@@unique([identifier, token])
}

model Movie {
id String @id @default(auto()) @map("_id") @db.ObjectId
title String
description String
videoUrl String
thumbnailUrl String // 缩略网址
genre String // 类型
duration String
}

接着在终端运行命令:npx prisma db push,将schema.prisma文件中定义的数据模型上传到云端,在mongodb的网页端选择database-browse collections,即可看到定义的5个数据模型。这说明prisma已经成功和mongodb连接起来了。

接着进入pages/api/hello.ts,可以通过链接:http://localhost:1689/api/hello访问到其中的内容。删除hello.ts,新建`[...nextauth].ts`文件,其会被next app识别。我们在这个文件中写next auth的middleware。通过命令npm install next-auth安装next-auth。还需要运行命令:npm install bcrypt。这个包用于用户名密码登录。在[...nextauth].ts文件中写下以下的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import NextAuth from 'next-auth';
import Credentials from 'next-auth/providers/credentials';
import { compare } from 'bcrypt';

import prismadb from '@/lib/prismadb';

export default NextAuth({
providers: [
Credentials({
id: 'credentials',
name: 'Credentials',
credentials: {
email: {
label: 'Email',
type: 'text',
},
password: {
label: 'Password',
type: 'password',
}
},
async authorize(credentials) {
if (!credentials?.email || !credentials?.password) {
throw new Error('Email and password required');
}

// 通过email找到用户,需要import prismadb
const user = await prismadb.user.findUnique({
where: {
email: credentials.email
}
});

// 判断找到的user是否存在
if (!user || !user.hashedPassword) {
throw new Error('Email does not exist');
}

// 判断用户输入的密码是否正确
const isCorrectPassword = await compare(
credentials.password,
user.hashedPassword
);

if (!isCorrectPassword) {
throw new Error("Incorrect password");
}

return user; // 用户密码输入正确,则返回由email找到的唯一user
}
})
],

pages: {
signIn: '/auth',
},
// debug on
debug: process.env.NODE_ENV === 'development',

session: {
strategy: 'jwt',
},
})

.env文件中加入以下两个环境变量:

1
2
NEXTAUTH_JWT_SECRET = "NEXT-JWT-SECRET"
NEXTAUTH_SECRET = "NEXT-SECRET"

[...nextauth].ts文件中添加以下的内容:

1
2
3
4
5
    jwt: {
secret: process.env.NEXTAUTH_JWT_SECRET,
},
secret: process.env.NEXTAUTH_SECRET,
});

接下来修复bcrypt标红的报错。在终端输入命令:npm i -D @types/bcrypt。安装了bcrypt后,不再标红报错。

进入pages/auth.tsx。在其中添加login和register的函数。首先通过命令行安装axios: npm i axios。然后在auth.tsx中引入axios并定义register函数:

1
2
3
4
5
6
import axios from "axios";

// register function
const register = useCallback(async () => {

}, []); // dependency: []

接着写下完整的register函数:

1
2
3
4
5
6
7
8
9
10
11
12
// register function
const register = useCallback(async () => {
try {
await axios.post('/api/register', {
email,
name,
password
});
} catch (error) {
console.log(error);
}
}, []); // dependency: []

接着在pages/api中定义register。在register.ts中写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import bcrypt from 'bcrypt';
import { NextApiRequest, NextApiResponse } from 'next';
import prismadb from '@/lib/prismadb';

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
if (req.method !== 'POST') {
return res.status(405).end(); // we only want to allow post calls to /api/register
}

// try and catch block
// try: extract some values from request.body
try {
const { email, name, password } = req.body;

// check if an email is already in use
const existinguser = await prismadb.user.findUnique({
where: {
email,
}
});

// email in use, return Email taken
if (existinguser) {
return res.status(422).json({error: 'Email taken'});
}

// hash the password
const hashedPassword = await bcrypt.hash(password, 12);

// 将user信息存入数据库
const user = await prismadb.user.create({
data: {
email,
name,
hashedPassword,
image: '',
emailVerified: new Date(),
}
});

return res.status(200).json(user);
} catch (error) {
console.log(error);
return res.status(400).end();
}
}

这就完成了/api/register。在auth.tsx中填入dependency的具体内容:[email, name, password]); // dependency in []

接着,我们需要在点击sign up按钮时呼叫/api/register。先不管按钮上写的是login还是register,将按钮统一绑定到register函数:

1
2
<button onClick={register} className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">
{variant === 'login' ? 'Login': 'Sign up'}

打开网页,F12打开调试模式,选择network,输入用户名、邮箱和密码,可以看到register函数被成功调用。接着打开mongodb atlas的网站,选择database-browse collections-user,可以看到其中添加了一条用户信息的数据,成功!到此,用户名密码注册部分完成了。

现在开始做Login部分。在auth.tsx中添加以下login函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// login function
const login = useCallback(async () => {
// try and catch block
try {
// 需要用到[..nextauth].ts中的Credentials
await signIn('credentials', {
email,
password,
redirect: false,
callbackUrl: '/'
});
} catch (error) {
console.log(error);
}
}, [email, password]); // login only need email and password

接着在按钮处调用login函数:

1
<button onClick={variant === 'login' ? login : register} className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">

这样就可以在点击login按钮时调用login函数,在点击sign up按钮时调用register函数。点击login按钮,网页并没有产生预期的跳转,打印出错误信息:Error: This action with HTTP GET is not supported by NextAuth.js。尝试修复这个问题。在api文件夹中再创建auth文件夹,将[...nextauth].ts文件拖拽到其中。然后这个问题就被修复了。接着继续在login函数中添加router:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const router = useRouter(); 

// login function
const login = useCallback(async () => {
// try and catch block
try {
// 需要用到[..nextauth].ts中的Credentials
await signIn('credentials', {
email,
password,
redirect: false,
callbackUrl: '/'
});

router.push('/');
} catch (error) {
console.log(error);
}
}, [email, password, router]); // login only need email and password, and then we add router

接着在register函数中添加login部分,一旦注册成功后就自动登录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// register function
const register = useCallback(async () => {
try {
await axios.post('/api/register', {
email,
name,
password
});

login();
} catch (error) {
console.log(error);
}
}, [email, name, password, login]); // dependency in []

同时注意调整login和register函数的顺序,让login定义在register之前(因为register中需要调用login函数)。现在再次尝试输入邮箱和密码并点击login按钮,发现可以成功跳转到根目录。

Google and Github OAuth

加入Google and Github OAuth非常简单。首先在终端中运行命令:npm install react-icons。通过这个包可以向项目中添加Google, Github和其他炫酷的icon。接下来写google和github一键登录的UI界面。在auth.tsx中加入以下代码。首先是引入react中包含icons的包,然后在login/sign up按钮下定义一个div,用于空出更大的空间。再定义一个div,用于存放按钮。在这个div中定义按钮的各种属性(居中、圆角等)。最后再通过FcGoogle引入Google的图标。接着,我们复制上面的代码,将图标改为Github。以上的代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import { FcGoogle } from 'react-icons/fc';
import { FaGithub } from 'react-icons/fa';

<div className="flex flex-row items-center gap-4 mt-8 justify-center">
<div
className="
w-10
h-10
bg-white
rounded-full
flex
items-center
justify-center
cursor-pointer
hover:opacity-80
transition
"
>
<FcGoogle size={30} />
</div>

<div
className="
w-10
h-10
bg-white
rounded-full
flex
items-center
justify-center
cursor-pointer
hover:opacity-80
transition
"
>
<FaGithub size={30} />
</div>
</div>

接着进入.env文件中增加一些环境变量。如下所示:

1
2
3
4
5
GITHUB_ID=
GITHUB_SECRET=

GOOGLE_CLIENT_ID=
GOOGLE_CLIENT_SECRET=

接着在[...nextauth].ts文件中添加包和GithubProvider、GoogleProvider。

1
2
3
4
5
6
7
8
9
10
11
import GithubProvider from 'next-auth/providers/github';
import GoogleProvider from 'next-auth/providers/google';

GithubProvider({
clientId: process.env.GITHUB_ID || '',
clientSecret: process.env.GITHUB_SECRET || ''
}),
GoogleProvider({
clientId: process.env.GOOGLE_CLIENT_ID || '',
clientSecret: process.env.GOOGLE_CLIENT_SECRET || ''
}),

接着执行命令:npm install @next-auth/prisma-adapter。接着在[...nextauth].ts文件中添加以下代码:

1
2
3
import { PrismaAdapter } from '@next-auth/prisma-adapter';

adapter: PrismaAdapter(prismadb),

接下来填入.env文件中的GITHUB_ID和GITHUB_SECRET。去到GITHUB-SETTINGS-DEVELOPER SETTINGS-OAUTH APPS-NEW OAUTH APP,填入以下内容:

1
2
3
4
5
6
7
8
9
Register a new OAuth application
Application name
netflix-clone

Homepage URL
http://localhost:1689

Authorization callback URL
http://localhost:1689

接着点击register application,然后将生成的GITHUB_ID和GITHUB_SECRET复制到.env文件中。

现在我们在auth.tsx中给github一键登录写一个函数:

1
onClick={() => signIn('github', { callbackUrl: '/' })}

并在.env文件中指定重定向URL的路径:NEXTAUTH_URL=http://localhost:10564/
进行上述操作后,github一键登录成功,一键登录成功后被导航回到了根目录。然后可以在mongodb的account中看到一条新的数据。本来应该在user中也看到一条新的数据,但我的user中没有github一键登录产生的新user的数据。这个问题在github的issues中有解释:https://github.com/AntonioErdeljac/next-netflix-tutorial/issues/13。这个问题应该不是一个问题,不用担心。

现在开始完成google一键登录。相比于github,Google会更麻烦些。进入google cloud console: https://console.cloud.google.com/welcome?pli=1&project=advance-proton-400620。新建项目并填入项目名称,点创建。选中该项目,搜索apis & services。选择oauth权限请求页面,选择外部,点击创建。填入应用名称、用户支持电子邮件、开发者联系信息,然后保存并继续。然后一路点击保存并继续。点击凭据-创建凭据-创建 OAuth 客户端 ID。选择web应用-添加URL:http://localhost:10564/api/auth/callback/google。我们就可以得到client ID和client secret。将它们复制到.env文件中。然后在auth.tsx中给google一键登录写一个函数:

1
onClick={() => signIn('google', { callbackUrl: '/' })}

在网页端尝试点击google一键登录,成功!

Protecting routes, Profiles screen

如何通过授权登录保护client路径和api路径。在lib文件夹中创建serverAuth.ts。在其中写下如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import { NextApiRequest } from 'next';
import { getSession } from 'next-auth/react';

import prismadb from '@/lib/prismadb';
import { error } from 'console';

const serverAuth = async (req: NextApiRequest) => {
// fetch log in user session
const session = await getSession({ req });

// use serverAuth in api controller
// req parameter will hold jwt token to get logged in user
// use session to get other fields
if (!session?.user?.email) {
throw new Error('Not signed in');
}

// 通过email找到不同的user
const currentUser = await prismadb.user.findUnique({
where: {
email: session.user.email,
}
});

// 无currentUser, 说明jwt token或者session不正确或者过期了
if (!currentUser) {
throw new Error('Not signed in');
}

return { currentUser };
}

export default serverAuth;

用上述文件可以在所有的api routes中检查我们是否登录。进入pages/api中,创建current.ts,在其中写上以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import { NextApiRequest, NextApiResponse } from 'next';

import serverAuth from '@/lib/serverAuth';

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
if (req.method !== 'GET') {
return res.status(405).end();
}

// try and catch block
try {
const { currentUser } = await serverAuth(req);

return res.status(200).json(currentUser);
} catch (error) {
console.log(error);
return res.status(400).end();
}
}

下面开始写用于front end fetching的部分,在libs/fetcher.ts,在其中写下代码:

1
2
3
4
5
import axios from 'axios';

const fetcher = (url: string) => axios.get(url).then((res) => res.data);

export default fetcher;

在前端写用于载入当前用户的代码。在根目录下新建hooks文件夹,在其中新建文件useCurrentUser.ts。然后在终端中运行命令:npm install swr。然后在useCurrentUser.ts中写入:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import useSWR from 'swr';

import fetcher from '@/lib/fetcher';

// svr: versal developed package, which is good at fetching data
// If the data already exists, we are not going to fetch the data again
const useCurrentUser = () => {
const { data, error, isLoading, mutate } = useSWR('/api/current', fetcher)

return {
data,
error,
isLoading,
mutate
}
};

export default useCurrentUser;

下面我们来展示如何保护client routes。我们想让用户在不登陆的情况下访问不到我们的网站。在pages/index.tsx中首先创建一个sign out按钮。

1
<button className="h-10 w-full bg-white" onClick={() => signOut()}>Logout!</button>

接下来我们来演示如何在pages/index.tsx中保护家路径。在其中写下以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import { NextPageContext } from "next";
import { getSession, signOut } from "next-auth/react";

// fetch our session from client side
// cannot use serverAuth
export async function getServerSideProps(context: NextPageContext) {
const session = await getSession(context);

// session不存在,则返回登录界面
if (!session) {
return {
redirect: {
destination: '/auth',
permanent: false,
}
}
}

// session存在,则返回空
return {
props: {}
}
}

export default function Home() {
return (
<>
<h1 className="text-4xl text-green-500">Netflix Clone</h1>
<button className="h-10 w-full bg-white" onClick={() => signOut()}>Logout!</button>
</>
);
}

现在实现了功能:用户不能在未登录的情况下直接访问家目录。现在的问题:登出以后无法登录并进入到家目录。进入mongodb-network access。点击add ip address,选择allow access from anywhere。目前项目仍然不能正常登录。报错信息显示:

1
2
3
4
5
6
7
8
9
10
11
12
[next-auth][error][CLIENT_FETCH_ERROR] 
https://next-auth.js.org/errors#client_fetch_error fetch failed {
error: {
message: 'fetch failed',
stack: 'TypeError: fetch failed\n' +
' at node:internal/deps/undici/undici:12443:11\n' +
' at process.processTicksAndRejections (node:internal/process/task_queues:95:5)',
name: 'TypeError'
},
url: 'http://localhost:10564/api/auth/session',
message: 'fetch failed'
}

我尝试了若干种解决办法,最后是这样解决的:
由于在默认情况下,port和forwarded address是不同的,这样就会导致上面的报错,我猜测是产生了跨域问题,导致port和forwarded address之间的信息转发失败了。我们需要将port和forwarded address的端口号改成相同的,并在.env文件和package.json文件中做出相应的修改。以我在本项目中的实际操作为例。我将port改为10564,将forwarded address也改为10564(vscode-PORTS中会自动补全为localhost:10564),然后在.env文件中添加:

1
NEXTAUTH_URL="http://localhost:10564"

package.json文件中添加:

1
2
3
4
"scripts": {
"dev": "next dev -p 10564",
"start": "next start -p 10564",
},

然后重启项目,就可以成功地通过用户名密码/github/google登入登出根页面了。

接下来关注如何通过useCurrentUser.ts中的hook来获取用户信息。在index.tsx中加入以下代码:

1
2
3
4
5
import useCurrentUser from "@/hooks/useCurrentUser";

const { data : user } = useCurrentUser();

<p className="text-white">Logged in as : {user?.email}</p>

这样在根页面就会显示Logged in as + 登录用户邮箱的信息。现在我们来创建用户档案页面。在pages文件夹下创建profiles.tsx文件,在其中加入以下框架:

1
2
3
4
5
6
7
8
9
const Profiles = () => {
return (
<div>
<p className="text-white text-4xl">Profiles</p>
</div>
)
};

export default Profiles;

接着访问http://localhost:10564/profiles,就可以看到白色的Profiles字样。接着在`profiles.tsx`文件中写`fetch session`的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// fetch our session from client side, just like  what we do in index.tsx
export async function getServerSideProps(context: NextPageContext) {
const session = await getSession(context); // get session

if (!session) {
return {
redirect: {
destination: '/auth',
permanent: false,
}
}
}

return {
props: {}
}
}

接着在auth.tsx中,将三个登录处的重定向URL重定向到profiles页面并删除router。现在产生了效果:在未登录时访问profiles页面会被重定向到auth页面。在auth页面登录后会被重定向到profiles页面。从github仓库中下载default blue图片,作为用户的默认头像。在profiles.tsx中写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const Profiles = () => {
const { data: user } = useCurrentUser();

return (
<div className="flex items-center h-full justify-center">
<div className="flex flex-col">
<h1 className="text-3xl md:text-6xl text-white text-center" >Who is watching?</h1>
<div className="flex items-center justify-center gap-8 mt-10">
<div onClick={() => {}}>

<div className="group flex-row w-44 mx-auto">
<div
className="
w-44
h-44
rounded-md
flex
items-center
justify-center
border-2
border-transparent
group-hover:cursor-pointer
group-hover:border-white
overflow-hidden
"
>
<img src="/images/default-blue.png" alt="Profile" />
</div>
<div
className="
mt-4
text-gray-400
text-2xl
text-center
group-hover:text-white
"
>
{user?.name}
</div>
</div>
</div>
</div>
</div>
</div>
)
};

产生了如下的效果:
Snipaste_2024-02-25_04-32-09.png

然后让点击图片会重定向回到根网页。增加以下代码即可:

1
2
3
const router = useRouter()

<div onClick={() => router.push('/')}>

清理index.tsx文件,只剩下骨架即可(不需要按钮和sign out功能):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import { NextPageContext } from "next";
import { getSession } from "next-auth/react";

// fetch our session from client side
// cannot use serverAuth
export async function getServerSideProps(context: NextPageContext) {
const session = await getSession(context);

// session不存在,则返回登录界面
if (!session) {
return {
redirect: {
destination: '/auth',
permanent: false,
}
}
}

// session存在,则返回空
return {
props: {}
}
}

export default function Home() {

return (
<>
</>
);
}

我们需要在上述文件中添加Navbar,但目前Navbar尚不存在,因此需要在components文件夹中添加Navbar.tsx

1
2
3
4
5
6
7
8
9
const Navbar = () => {
return (
<div>
Navbar
</div>
)
}

export default Navbar;

然后在index.tsx中import并添加Navbar。接下来在Navbar.tsx中写入具体的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const Navbar = () => {
return (
// navigation type
<nav className="w-full fixed z-40">
<div
className="
px-4
md:px-16
py-6
flex
flex-row
items-center
transition
duration-500
bg-zinc-900
bg-opacity-90
"
>
<img className="h-4 lg:h-7" src="/images/logo.png" alt="Logo" />
<div
className="
flex-row
ml-8
gap-7
hidden
lg:flex
"
>
<NavbarItem />
</div>
</div>
</nav>
)
}

export default Navbar;

接着在components中定义NavbarItem.tsx,写出其骨架:

1
2
3
4
5
6
7
8
9
const NavbarItem = () => {
return (
<div>

</div>
)
}

export default NavbarItem;

接着丰满其中的细节:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import React from 'react';

interface NavbarItemProps {
label: string;

}

const NavbarItem: React.FC<NavbarItemProps> = ({
label
}) => {
return (
<div className="text-white cursor-pointer hover:text-gray-300 trasition">
{label}
</div>
)
}

export default NavbarItem;

需要从Navbar.tsx中传入label: <NavbarItem label="Home" />,并依照同样的方式创建另外几个导航组件:

1
2
3
4
5
6
7
8
9
10
<NavbarItem label="Home" />
<NavbarItem label="Series" />
<NavbarItem label="Films" />
<NavbarItem label="New & Popular" />
<NavbarItem label="My List" />
<NavbarItem label="Browse by languages" />

<div className="lg:hidden flex flex-row items-center gap-2 ml-8 cursor-pointer relative">
<p className="text-white text-sm">Browse</p>
</div>

小屏幕时,只出现Browse,不出现其他navagation component。接着去查找icons: https://react-icons.github.io/react-icons/。找到一个向下展开的小箭头,在`Navbar.tsx`中引入并使用这个小箭头:

1
2
3
import { BsChevronDown } from 'react-icons/bs';

<BsChevronDown className="text-white transition" />

接着创建手机端(小屏幕)的菜单。先在components中创建MobileMenu.tsx,在其中写以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import React from 'react';

interface MobileMenuProps {
visible?: boolean;
}

const MobileMenu: React.FC<MobileMenuProps> = ({ visible }) => {
if (!visible) {
return null;
}

return (
<div className="bg-black w-56 absolute top-8 left-0 py-5 flex-col border-2 border-gray-800 flex">
<div className='flex flex-col gap-4'>
<div className='px-3 text-center text-white hover:underline'>
Home
</div>
</div>
</div>
)
};

export default MobileMenu;

然后在Navbar.tsx中引入MobileMenu。并实现手机(小屏幕)上点击browse展开出home的功能

1
2
3
4
5
6
7
const [showMobileMenu, setShowMobileMenu] = useState(false);

const toggleMobileMenu = useCallback(() => {
setShowMobileMenu((current) => !current);
}, []);

<MobileMenu visible={showMobileMenu} />

对于上述代码的解释:这段代码是使用React Hooks编写的,主要用于在React组件中管理和切换移动设备菜单的显示状态。具体来说,这段代码定义了一个状态变量showMobileMenu和一个切换该状态的函数toggleMobileMenu。下面是这段代码的详细解释:

useState 钩子

1
const [showMobileMenu, setShowMobileMenu] = useState(false);
  • useState是一个React Hook,允许在函数组件中添加状态。这里,它被用来定义一个名为showMobileMenu的状态变量,用于跟踪移动菜单是否显示。该状态的初始值为false,意味着菜单默认是不显示的。
  • setShowMobileMenu是一个函数,用于更新showMobileMenu状态的值。当调用这个函数并传入一个新的值时,组件会重新渲染,并且showMobileMenu的值会更新为传入的新值。

useCallback 钩子

1
2
3
const toggleMobileMenu = useCallback(() => {
setShowMobileMenu((current) => !current);
}, []);
  • useCallback是另一个React Hook,它返回一个记忆化的回调函数。这个回调函数只会在依赖项数组(这里是空数组[])中的值发生变化时才会更新。在这个例子中,由于依赖项数组为空,toggleMobileMenu函数在组件的整个生命周期内保持不变。
  • toggleMobileMenu函数的作用是调用setShowMobileMenu来切换showMobileMenu状态的值。它通过传递一个函数给setShowMobileMenu,这个函数接收当前的状态值current作为参数,并返回其相反值!current。这样,如果菜单当前是显示的(true),调用toggleMobileMenu会将其隐藏(设为false),反之亦然。

总结

这段代码的主要目的是控制移动菜单的显示状态。通过点击或触发某个事件来调用toggleMobileMenu函数,可以在显示和隐藏移动菜单之间切换,从而为用户提供一个响应式的导航体验。这种模式在开发响应式Web应用时非常常见,特别是在需要改进移动设备上的用户界面和交互时。

进入MobileMenu.tsx中,加入一些新的class。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<div className='px-3 text-center text-white hover:underline'>
Home
</div>
<div className='px-3 text-center text-white hover:underline'>
Series
</div>
<div className='px-3 text-center text-white hover:underline'>
Films
</div>
<div className='px-3 text-center text-white hover:underline'>
New & Popular
</div>
<div className='px-3 text-center text-white hover:underline'>
My List
</div>
<div className='px-3 text-center text-white hover:underline'>
Browse by Languages
</div>

这样点开browse就会展开上述的内容。接下来是profile menu。首先在导航组件中添加一个search(即一个放大镜形状的图标)。再添加一个铃铛,最后添加用户的默认头像,然后在用户头像处也添加一个向下展开的箭头。在Navbar.tsx中使用如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<div className="flex flex-row ml-auto gap-7 items-center">
<div className="text-gray-200 hover:text-gray-300 cursor-pointer transition">
<BsSearch />
</div>
<div className="text-gray-200 hover:text-gray-300 cursor-pointer transition">
<BsBell />
</div>
<div className="flex flex-row items-center gap-2 cursor-pointer relative">
<div className="w-6 h-6 lg:w-10 lg:h-10 rounded-md overflow-hidden">
<img src="/images/default-blue.png" alt="" />
</div>
<BsChevronDown className="text-white transition" />
</div>
</div>

再添加AccountMenu。先在components中定义AccountMenu.tsx,在其中写一个骨架:

1
2
3
4
5
6
7
8
9
const AccountMenu = () => {
return (
<div>

</div>
)
}

export default AccountMenu;

然后再在Navbar.tsx中引入AccountMenu。在AccountMenu.tsx中写入具体的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import { signOut } from "next-auth/react";
import React from "react";

interface AccountMenuProps {
visible: boolean;

}

const AccountMenu: React.FC<AccountMenuProps> = ({
visible
}) => {
if (!visible) {
return null;
}

return (
<div className="bg-black w-56 absolute top-14 right-0 py-5 flex-col border-2 border-gray-800 flex">
<div className="flex flex-col gap-3">
<div className="px-3 group/item flex flex-row gap-3 items-center w-full">
<img className="w-8 rounded-md" src="/images/default-blue.png" alt="" />
<p className="text-white text-sm group-hover/item:underline">
Username
</p>
</div>
</div>
</div>
)
}

export default AccountMenu;

Navbar.tsx中加入<AccountMenu visible/>,让AccountMenu。接下来再在AccountMenu.tsx中加入signOut按钮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
return (
<div className="bg-black w-56 absolute top-14 right-0 py-5 flex-col border-2 border-gray-800 flex">
<div className="flex flex-col gap-3">
<div className="px-3 group/item flex flex-row gap-3 items-center w-full">
<img className="w-8 rounded-md" src="/images/default-blue.png" alt="" />
<p className="text-white text-sm group-hover/item:underline">
Username
</p>
</div>
<hr className="bg-gray-600 border-0 h-px my-4" />
<div onClick={() => signOut()} className="px-3 text-center text-white text-sm hover:underline">
Sign out of Netflix
</div>
</div>
</div>
)

然后还需要加入展开AccountMenu和收起AccountMenu的功能。在Navbar.tsx中加入代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const [showAccountMenu, setShowAccountMenu] = useState(false);

const toggleAccountMenu = useCallback(() => {
setShowAccountMenu((current) => !current);
}, []);


<div onClick={toggleAccountMenu} className="flex flex-row items-center gap-2 cursor-pointer relative">
<div className="w-6 h-6 lg:w-10 lg:h-10 rounded-md overflow-hidden">
<img src="/images/default-blue.png" alt="" />
</div>
<BsChevronDown className="text-white transition" />
<AccountMenu visible={showAccountMenu} />
</div>

然后加入旋转 控制AccountMenu展开和收起的箭头的功能。

1
<BsChevronDown className={`text-white transition ${showAccountMenu ? `rotate-180` : `rotate-0`}`} />

同理,对控制browse的箭头也做相同的处理。

1
<BsChevronDown className={`text-white transition ${showMobileMenu ? `rotate-180` : `rotate-0`}`} />

现在想加一个特效:向下滑动时页面变黑,其他情况下页面透明。在Navbar.tsx中加入以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const [showBackground, setShowBackground] = useState(false);

useEffect(() => {
const handleScroll = () => {
if (window.scrollY >= TOP_OFFSET) {
setShowBackground(true);
} else {
setShowBackground(false);
}
}

window.addEventListener('scroll', handleScroll); // listen to scroll event

return () => {
window.removeEventListener('scroll', handleScroll); // remove listener
}
}, []);

<nav className="w-full fixed z-40">
<div
className={`
px-4
md:px-16
py-6
flex
flex-row
items-center
transition
duration-500
${showBackground ? 'bg-zinc-900 bg-opacity-90' : ''}

`}

加上这些代码后,当滚动页面时,导航组件都是透明的,但当开始滑动鼠标滚轮时,导航组件的背景变为黑色。
可以在index.sh中添加代码来测试这个功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
export default function Home() {

return (
<>
<Navbar />
<div className="bg-gray-500">
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
<div className="h-96"></div>
</div>
</>
);
}

添加完上述代码后,页面可以滚动,发现功能是正常的。

Billboard Component, Random Movie Endpoint

每次会随机加载一部电影。进入github仓库,打开movies.json。将其中的电影全部加入到数据库中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
[
{
"title":"Big Buck Bunny",
"description":"Three rodents amuse themselves by harassing creatures of the forest. However, when they mess with a bunny, he decides to teach them a lesson.",
"videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/BigBuckBunny.mp4",
"thumbnailUrl":"https://upload.wikimedia.org/wikipedia/commons/7/70/Big.Buck.Bunny.-.Opening.Screen.png",
"genre":"Comedy",
"duration":"10 minutes"
},
{
"title":"Sintel",
"description":"A lonely young woman, Sintel, helps and befriends a dragon, whom she calls Scales. But when he is kidnapped by an adult dragon, Sintel decides to embark on a dangerous quest to find her lost friend Scales.",
"videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/Sintel.mp4",
"thumbnailUrl":"http://uhdtv.io/wp-content/uploads/2020/10/Sintel-3.jpg",
"genre":"Adventure",
"duration":"15 minutes"
},
{
"title":"Tears of Steel",
"description":"In an apocalyptic future, a group of soldiers and scientists takes refuge in Amsterdam to try to stop an army of robots that threatens the planet.",
"videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/TearsOfSteel.mp4",
"thumbnailUrl":"https://mango.blender.org/wp-content/uploads/2013/05/01_thom_celia_bridge.jpg",
"genre":"Action",
"duration":"12 minutes"
},
{
"title":"Elephant's Dream",
"description":"Friends Proog and Emo journey inside the folds of a seemingly infinite Machine, exploring the dark and twisted complex of wires, gears, and cogs, until a moment of conflict negates all their assumptions.",
"videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/ElephantsDream.mp4",
"thumbnailUrl":"https://download.blender.org/ED/cover.jpg",
"genre":"Sci-Fi",
"duration":"15 minutes"
}
]

上述json文件中的数据格式和schema.prisma中的movies数据类型中定义的内容相同,除了缺少由mongodb产生的id。在mongodb网站中选择database-browse collections-movie-insert document,将json文件中的内容粘贴进去即可。现在就完成了对数据模型movie的修改。

现在创建一条新的路径:random。在pages/api/random.ts中写下以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// random movie will be loaded every time we refresh the page
import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
// limit request method to GET
if (req.method !== 'GET') {
return res.status(405).end();
}

// try and catch block
try {
// check if the user log in
await serverAuth(req);

const movieCount = await prismadb.movie.count();
const randomIndex = Math.floor(Math.random() * movieCount); // a random integar

const randomMovies = await prismadb.movie.findMany({
take: 1,
skip: randomIndex
});

return res.status(200).json(randomMovies[0]); // take only one movies
} catch (error) {
console.log(error);
return res.status(400).end();
};
}

hooks/useBillboard.ts中写下以下的代码,避免对首页推荐电影的重复加载:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import useSWR from "swr";

import fetcher from "@/lib/fetcher";

const useBillboard =() => {
const { data, error, isLoading } = useSWR('/api/random', fetcher, {
// static data only load once the user visits the page
// not every time they lose focus out of the window
revalidateIfStale: false,
revalidateOnFocus: false,
revalidateOnReconnect: false,
});

return {
data,
error,
isLoading,
}
}

export default useBillboard;

components中新建Billboard.tsx,并在其中搭建一个骨架:

1
2
3
4
5
6
7
8
9
10
11
import React from "react";

const Billboard = () => {
return (
<div>

</div>
)
}

export default Billboard;

然后在index.tsx中引入Billboard。接着在Billboard.tsx中填入具体的内容,目的是fetch the data for a random movie。

1
2
3
4
5
6
7
8
9
10
11
12
13
import useBillboard from "@/hooks/useBillboard";
import React from "react";

const Billboard = () => {
const { data } = useBillboard();
return (
<div>

</div>
)
}

export default Billboard;

可以打开网页的调试界面:network-random-preview,就可以看到随机选择的电影的信息。接着继续写Billboard.tsx,在Billboard中添加随机的电影、电影名、电影介绍和More info按钮:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import useBillboard from "@/hooks/useBillboard";
import React from "react";

import { AiOutlineInfoCircle } from "react-icons/ai";

const Billboard = () => {
const { data } = useBillboard();
return (
<div className="relative h-[56.25vw]">
<video
className="
w-full
h-[56.25vw]
object-cover
brightness-[60%]
"
autoPlay
muted
loop
poster={data?.thumbnailUrl}
src={data?.videoUrl}>
</video>
<div className="absolute top-[30%] md:top-[40%] ml-4 md:ml-16">
<p className="
text-white
text-1xl
md:text-5xl
h-full
w-[50%]
lg:text-6xl
font-bold
drop-shadow-xl
">
{data?.title}
</p>
<p className="
text-white
text-[8px]
md:text-lg
mt-3
md:mt-8
w-[90%]
md:w-[80%]
lg:w-[50%]
drop-shadow-xl
">
{data?.description}
</p>
<div className="flex flex-row items-center mt-3 md:mt-4 gap-3">
<button
className="
bg-white
text-white
bg-opacity-30
rounded-md
py-1 md:py-2
px-2 md:px-4
w-auto
text-xs lg:text-lg
font-semibold
flex
flex-row
items-center
hover:bg-opacity-20
transition
"
>
<AiOutlineInfoCircle className="mr-1" />
More Info
</button>
</div>
</div>
</div>
)
}

export default Billboard;

本节到此结束,效果图如下所示:
Snipaste_2024-02-27_04-40-46.png

补充

await和async的区别和联系:在TypeScript中,asyncawait关键字一起使用,作为处理异步操作的一种方式,主要用于替代传统的回调函数和Promise。它们两者之间有着明确的区别和各自的用途:

async

  • async关键字用于声明一个异步函数,它让函数自动返回一个Promise。这意味着,当你在一个函数声明前加上async,这个函数就会返回一个Promise,而不是直接返回值。
  • 使用async,你可以在函数内部使用await表达式。
  • async函数可以包含零个或多个await表达式。

例子:

1
2
3
4
async function fetchData() {
// 函数返回一个Promise
return "data";
}

在这个例子中,fetchData函数返回一个解析为字符串”data”的Promise。

await

  • await关键字用于等待一个Promise解析,它只能在async函数内部使用。
  • await前面的Promise被解析后,函数执行会继续,await表达式的结果就是Promise解析的值。
  • 使用await可以让异步代码看起来像是同步代码,这使得代码更容易理解和维护。

例子:

1
2
3
4
async function showData() {
const data = await fetchData(); // 等待fetchData解析
console.log(data);
}

在这个例子中,showData函数内部调用了fetchData函数,并在其Promise解析之后继续执行,打印出解析后的数据。

总结

  • async是一个使函数返回Promise的修饰符,而await是用于等待Promise解析的操作符。
  • await只能在async函数内部使用。
  • 它们一起使用提供了一种更简洁和直观的方式来处理JavaScript中的异步操作,避免了回调地狱(Callback Hell)的问题。

Movie List & Movie Card Components, Movies Endpoint, Cool hover effect

在pages/api中创建一个新的movies文件夹。在其中创建index.ts,并在其中写入这个api的具体内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from '@/lib/serverAuth';

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
// this api call only get request method
if (req.method !== 'GET') {
return res.status(405).end();
}

// try and catch block
try {
await serverAuth(req); // authenticate this route

// load all the movies
const movies = await prismadb.movie.findMany();

return res.status(200).json(movies);

} catch (error) {
console.log(error);
return res.status(400).end();
}
}

接着再创建一个hook。在hook文件夹中创建useMovieList.ts。并写入以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import useSWR from "swr";
import fetcher from "@/lib/fetcher";

const useMovieList = () => {
const { data, error, isLoading } = useSWR('api/movies', fetcher, {
// 不需要重新验证
revalidateIfStale: false,
revalidateOnFocus: false,
revalidateOnReconnect: false,
});

return {
data,
error,
isLoading
}
};

export default useMovieList;

接着进入pages/index.tsx,加入以下代码:

1
2
3
<div className="pb-40">
<MovieList />
</div>

由于我们有多个MovieList,因此需要将MovieList包裹在div中。接着我们创建MovieList。在components中创建MovieList.tsx,并在其中搭建一个骨架:

1
2
3
4
5
6
7
const MovieList = () => {
return (
<div></div>
)
}

export default MovieList;

接着丰满其中的细节:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import React from "react";

import { isEmpty } from 'lodash';

interface MovieListProps {
data: Record<string, any>[]; // type: array
title: string;
}

const MovieList: React.FC<MovieListProps> = ({ data, title }) => {
// do not render empty data
if (isEmpty(data)) {
return null;
}
return (
<div className="px-4 md:px-12 mt-4 space-y-8">
<div>
<p className="text-white text-md md:text-xl lg:text-2xl font-semibold mb-4">
{title}
</p>

<div className="grid grid-cols-4 gap-2">
{data.map((movie) => (
<div key={movie.id}>movie</div>
))}
</div>
</div>
</div>
)
}

export default MovieList;

记得安装必要的库:

1
2
npm install lodash
npm install -D @types/lodash

接着在pages/index.tsx中给MovieList传入必要的参数:

1
2
3
4
const { data: movies = [] } = useMovieList(); // use the newly created hook
<div className="pb-40">
<MovieList title="Trending Now" data={movies} />
</div>

产生了如下效果:
Snipaste_2024-02-28_23-51-30.png

现在将黑色的movies小字转换成实际的电影,并用上炫酷的Tailwind hover效果。在MovieList.tsx中加入下面的代码:

1
<MovieCard key={movie.id} data={movie} />

接着在components文件夹中创建MovieCard.tsx文件。填入以下的骨架:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import React from "react";

interface MovieCardProps {
data: Record<string, any>;
}

const MovieCard: React.FC<MovieCardProps> = ({
data
}) => {
return (
<div>

</div>
)
}

export default MovieCard;

接着继续丰满上述代码的细节:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import React from "react";
import { BsFillPlayFill } from "react-icons/bs";

interface MovieCardProps {
data: Record<string, any>;
}

const MovieCard: React.FC<MovieCardProps> = ({
data
}) => {
return (
<div className="group bg-zinc-900 col-span relative h-[12vw]">
<img
className="
cursor-pointer
object-cover
transition
duration
shadow-xl
rounded-md
group-hover:opacity-90
sm:group-hover:opacity-0
delay-300
w-full
h-[12vw]
"
src={data.thumbnailUrl} alt="Thumbnail" />
<div
className="
opacity-0
absolute
top-0
transition
duration-200
z-10
invisible
sm:visible
delay-300
w-full
scale-0
group-hover:scale-110
group-hover:-translate-y-[6vw]
group-hover:translate-x-[2vw]
group-hover:opacity-100
"
>
<img
className="
cursor-pointer
object-cover
transition
duration
shadow-xl
rounded-t-md
w-full
h-[12vw]
"
src={data.thumbnailUrl} alt="Thumbnail" />
<div
className="
z-10
bg-zinc-800
p-2
lg:p-4
absolute
w-full
transition
shadow-md
rounded-b-md
"
>
<div className="flex flex-row items-center gap-3">
<div
className="
cursor-pointer
w-6
h-6
lg:w-10
lg:h-10
bg-white
rounded-full
flex
justify-center
items-center
transition
hover:bg-neutral-300
"
onClick={() => {}}>
<BsFillPlayFill size={30} />
</div>
</div>

<p className="text-green-400 font-semibold mt-4">
New <span className="text-white">2024</span>
</p>

<div className="flex flex-row mt-4 gap-2 items-center">
<p className="text-white text-[10px] lg:text-sm">{data.duration}</p>
</div>

<div className="flex flex-row mt-4 gap-2 items-center">
<p className="text-white text-[10px] lg:text-sm">{data.genre}</p>
</div>
</div>
</div>
</div>
)
}

export default MovieCard;

最后实现的效果图如下所示:

Snipaste_2024-02-29_02-48-28.png

Favourites / My List functionality

本节我们将实现favourite按钮,其在播放按钮的旁边。我们还将在Trending List下面实现My List,其中将只展示我们favourite的电影。在pages/api/favorite.ts中写下以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// can handle both post request and delete request
// api to add and remove favourite ID in our list
import { NextApiRequest, NextApiResponse } from "next";
import { without } from "lodash";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
// try and catch block
try {
// handle post request
if (req.method === 'POST') {
const { currentUser } = await serverAuth(req); // get curent user

const { movieId } = req.body; // get movieId

// check if the movieId is correct
const existingMovie = await prismadb.movie.findUnique({
where: {
id: movieId,
}
});

if (!existingMovie) {
throw new Error('Invalid ID');
}

// update user and push movieId to their favoriteIds defined in schema.prisma
const user = await prismadb.user.update({
where: {
email: currentUser.email || '',
},
data: {
favoriteIds: {
push: movieId,
}
}
});

return res.status(200).json(user);
}

// handle delete request when a user want to unfavorite a movie
if (req.method === 'DELETE') {
const { currentUser } = await serverAuth(req);

const { movieId } = req.body;

const existingMovie = await prismadb.movie.findUnique({
where: {
id: movieId,
}
});

if (!existingMovie) {
throw new Error('Invalid ID');
}

// a list of our current favorite IDs without the above movie id
const updateFavoriteIds = without(currentUser.favoriteIds, movieId);

// update User information
const updatedUser = await prismadb.user.update({
where: {
email: currentUser.email || '',
},
data: {
favoriteIds: updateFavoriteIds,
}
});

return res.status(200).json(updatedUser);
}

return res.status(405).end();
} catch (error) {
console.log(error);
return res.status(400).end();
}
}

接下来创建一个api route,其将只加载我们最喜欢的电影列表。在pages/api/favorites.ts,写下如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// fetch all of our favorite movies
import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req:NextApiRequest, res: NextApiResponse) {
// limit this route only to get method
if (req.method !== 'GET') {
return res.status(405).end();
}

// try and catch block
try {
const { currentUser } = await serverAuth(req);

// find all movies which have a relation to current user favorite IDs
const favoriteMovies = await prismadb.movie.findMany({
where: {
id: {
in: currentUser?.favoriteIds,
}
}
});

return res.status(200).json(favoriteMovies);

} catch (error) {
console.log(error);
return res.status(400).end();
}
}

接着再写一个hook,用于加载最喜欢的电影列表。在hooks/useFavorites.ts中写入以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import useSWR from "swr";
import fetcher from "@/lib/fetcher";

const useFavorites = () => {
const { data, error, isLoading, mutate } = useSWR('/api/favorites', fetcher, {
revalidateIfStale: false,
revalidateOnFocus: false,
revalidateOnReconnect: false,
});

return {
data,
error,
isLoading,
mutate
}
};

export default useFavorites;

再写一个组件:components/FavoriteButton.tsx,作为按钮:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import axios from "axios";
import React, { useCallback, useMemo } from "react";

import useCurrentUser from "@/hooks/useCurrentUser";
import useFavorites from "@/hooks/useFavorites";

interface FavoriteButtonProps {
movieId: string;
}

// only one parameter: movieId
const FavoriteButton: React.FC<FavoriteButtonProps> = ({ movieId }) => {
return (
<div>

</div>
)
}

export default FavoriteButton;

将该按钮加在MovieCard中。在components/MovieCard.tsx中的播放按钮之后加入:

1
<FavoriteButton movieId={data?.id} />

补充知识:在JavaScript和TypeScript中,?操作符在这个上下文中被用作可选链(Optional Chaining)操作符。当你在一个对象后面加上?后跟属性名或方法,这意味着如果这个对象存在(即不是nullundefined),则会尝试访问该属性或方法;如果对象是nullundefined,则不会尝试访问该属性或方法,而是直接返回undefined。这避免了在访问深层嵌套对象属性时可能出现的类型错误。

接着写components/FavoriteButton.tsx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import axios from "axios";
import React, { useCallback, useMemo } from "react";
import { AiOutlinePlus } from "react-icons/ai";

import useCurrentUser from "@/hooks/useCurrentUser";
import useFavorites from "@/hooks/useFavorites";

interface FavoriteButtonProps {
movieId: string;
}

// only one parameter: movieId
const FavoriteButton: React.FC<FavoriteButtonProps> = ({ movieId }) => {
return (
<div className="
cursor-pointer
group/item
w-6
h-6
lg:w-10
lg:h-10
border-white
border-2
rounded-full
flex
justify-center
items-center
transition
hover:border-neutral-300
">
<AiOutlinePlus className="text-white" size ={25} />
</div>
)
}

export default FavoriteButton;

然后在Trending Now列表以外再创建一个My Favorites列表。进入pages/index.tsx中,增加以下的代码:

1
2
3
const { data: favorites = [] } = useFavorites(); // use hook to get favorite movies

<MovieList title="My List" data={favorites} />

由于目前还没有最喜欢的电影,因此My List为空。在FavoriteButton.tsx中添加以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const { mutate: mutateFavorites } = useFavorites();
const { data: currentUser, mutate } = useCurrentUser();

// check if the favorite list of current user includes movieId
const isFavorite = useMemo (() => {
const list = currentUser?.favoriteIds || [];

return list.include(movieId);
}, [currentUser, movieId]); // dependency in []

// once we click the favorite, we will check if the current movie is favorited
// if yes, trigger the delete request
// if no, add the movie in the favorite list
const toggleFavorites = useCallback(async () => {
let response;

if (isFavorite) {
response = await axios.delete('/api/favorite', { data: { movieId }});
} else {
response = await axios.post('/api/favorite', { movieId });
}

// update the favorite list of current user
const updatedFavoriteIds = response?.data?.favoriteIds;

// mutate用于更新currentUser数据
mutate({
...currentUser, // 复制了currentUser对象中的所有属性到一个新对象中
// 如果currentUser对象中已经存在favoriteIds属性,这一操作将会覆盖原有的值。如果不存在,就会添加一个新的favoriteIds属性
favoriteIds: updatedFavoriteIds,
});

mutateFavorites(); // 来自useFavorites中的mutate,每次更新currentUser的favoriteIds的数据后,立即刷新
}, [movieId, isFavorite, currentUser, mutate, mutateFavorites]);

实现了上述函数后,我们要让favorite按钮变得可交互。添加以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const Icon = isFavorite ? AiOutlineCheck : AiOutlinePlus;

return (
<div
onClick={toggleFavorites}
className="
cursor-pointer
group/item
w-6
h-6
lg:w-10
lg:h-10
border-white
border-2
rounded-full
flex
justify-center
items-center
transition
hover:border-neutral-300
">
<Icon className="text-white" size ={25} />
</div>
)

这样点击Trending Now列表上的电影上的加号时,其就会被添加到My List,然后加号会变成勾。这样一部电影就被选择为favorite了。同理,在My List中点击打勾符号,电影就会被取消选中,从My List里面消失。但目前该功能还是有bug。解决方法似乎是:https://github.com/nextauthjs/next-auth/issues/7199,需要将getSession替换为getServerSession。替换后问题得到了解决。

详细解决步骤:在[..nextauth].ts中添加AuthOptions,然后在serverAuth.ts中使用getServerSession替换getSession,并给getServerSession传入三个参数:req, res, authOptions,最后在所有用到serverAuth的api中将const { currentUser } = await serverAuth(req)替换为const { currentUser } = await serverAuth(req, res);。即可以修复上述bug。

Play Button, Video Player, Single Movie Endpoint

在billboard中加入播放按钮。还要创建player route。

首先创建pages/api/movies/[movieId].ts,在其中写入代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
// limit to get request
if (req.method !== 'GET') {
return res.status(405).end();
}

// try and catch block
try {
await serverAuth(req, res);

const { movieId } = req.query; // search for movie Id

if (typeof movieId !== 'string') {
throw new Error('Invalid ID');
}

if (!movieId) {
throw new Error('Invalid ID');
}

// find movie using movieId
const movie = await prismadb.movie.findUnique({
where: {
id: movieId
}
});

if (!movie) {
throw new Error('Invalid ID');
}

return res.status(200).json(movie);
} catch (error) {
console.log(error);
return res.status(400).end();
}
}

接着创建一个hook。创建hooks/useMovie.ts,在其中写入代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import useSWR from "swr";
import fetcher from "@/lib/fetcher";

// parameter: id,该id会被/api/movies/[movieId].ts中的[movieId]解析
const useMovie = (id?: string) => {
const {
data,
error,
isLoading
} = useSWR(id ? `/api/movies/${id}` : null, fetcher, {
revalidateIfStale: false,
revalidateOnFocus: false,
revalidateOnReconnect: false
});

return {
data,
error,
isLoading,
}
}

export default useMovie;

接着创建一个play按钮的component。创建components/PlayButton.tsx,在其中写入骨架:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import React from "react";
import { BsFillPlayFill } from "react-icons/bs";
import { useRouter } from 'next/router';

interface PlayButtonProps {
movieId: string;
}

const PlayButton: React.FC<PlayButtonProps> = ({ movieId }) =>{
const router = useRouter();

return (
<div>

</div>
)
};

export default PlayButton;

接着在components/Billboard.tsx中加入上述组件。在写有more info字样的按钮前加入:<PlayButton movieId={data?.id} />。接着继续丰满components/PlayButton.tsx中的细节:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import React from "react";
import { BsFillPlayFill } from "react-icons/bs";
import { useRouter } from 'next/router';

interface PlayButtonProps {
movieId: string;
}

const PlayButton: React.FC<PlayButtonProps> = ({ movieId }) =>{
const router = useRouter();

return (
<button
onClick={() => router.push(`/watch/${movieId}`)}
className="
bg-white
rounded-md
py-1 md:py-2
px-2 md:px-4
w-auto
text-xs lg:text-lg
font-semibold
flex
flex-row
items-center
hover:bg-neutral-300
transition
"
>
<BsFillPlayFill size={25} className="mr-1" />
Play
</button>
)
};

export default PlayButton;

现在就实现了点击播放按钮,跳转到另一个页面。接着在MovieCard组件中也实现上述点击播放然后跳转的功能。进入components/MovieCard.tsx,在其中添加代码:

1
2
3
import { useRouter } from 'next/router';
const router = useRouter();
onClick={() => router.push(`/watch/${data?.id}`)}>

现在需要具体写跳转到的页面。开始写/watch页面。创建pages/watch/[movieId].tsx,在其中写入以下的骨架:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// outside of api folder, so this is a client route
import React from "react";

import useMovie from "@/hooks/useMovie";
import { useRouter } from "next/router";

const Watch = () => {
const router = useRouter();
const { movieId } = router.query;

const { data } = useMovie(movieId as string);

return (
<div>

</div>
)
}

export default Watch;

现在点击播放按钮,会跳转到一个空白页面。继续丰满上述代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// outside of api folder, so this is a client route
import React from "react";
import { AiOutlineArrowLeft } from "react-icons/ai";
import useMovie from "@/hooks/useMovie";
import { useRouter } from "next/router";

const Watch = () => {
const router = useRouter();
const { movieId } = router.query;

const { data } = useMovie(movieId as string);

return (
<div className="h-screen w-screnn bg-black">
<nav
className="
fixed
w-full
p-4
z-10
flex-row
items-center
gap-8
bg-black
bg-opacity-70
"
>
<AiOutlineArrowLeft onClick={() => router.push('/')} className="text-white cursor-pointer" size={40} />
<p className="text-white text-1xl md:text-3xl font-bold">
<span className="font-light">
Watching:
</span>
{data?.title}
</p>
</nav>
<video
autoPlay
controls
className="h-full w-full"
src={data?.videoUrl}></video>
</div>
)
}

export default Watch;

现在就实现了功能:点击播放按钮,跳转到播放视频的页面,播放视频的页面会自动加载视频的名字,并有一个返回按钮,点击之可以返回到homepage。播放视频的页面中的视频可以播放、暂停、拖动时间条。

Info Modal Component

点击More Info按钮,会显示电影的信息。在Treanding Now下面会加一个展开按钮,会展开电影相关的信息。

创建hooks/useInfoModel.ts,并通过命令npm install zustand安装新的库。zustand是一个轻量化的全局状态管理库。在useInfoModel.ts中写入以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import { create } from "zustand";

export interface ModalStoreInterface {
movieId?: string;
isOpen: boolean;
openModal: (movieId: string) => void;
closeModal: () => void;
};

// hook
const useInfoModal = create<ModalStoreInterface>((set) => ({
movieId: undefined,
isOpen: false,
openModal: (movieId: string) => set({ isOpen: true, movieId }),
closeModal: () => set({ isOpen: false, movieId: undefined}),
}));

export default useInfoModal;

创建components/InfoModal.tsx,写入以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import React, { useCallback, useEffect, useState} from "react";
import { AiOutlineClose } from "react-icons/ai"; // close Button

import PlayButton from "./PlayButton"; // PlayButton
import FavoriteButton from "./FavoriteButton";
import useInfoModal from "@/hooks/useInfoModal";
import useMovie from "@/hooks/useMovie";

interface InfoModalProps {
visible?: boolean;
onClose: any;
};

const InfoModal: React.FC<InfoModalProps> = ({ visible, onClose }) => {
// a state for visible, visible is boolean so !! before it
const [isVisible, setIsVisible] = useState(!!visible);

// fetch moveId
const { movieId } = useInfoModal();
// fetch data from movie
const { data = {} } = useMovie(movieId);

// use Effect
useEffect(() => {
setIsVisible(!!visible); // set visible on every new visible change that we get
}, [visible]); // visible in dependency

const handleClose = useCallback(() => {
setIsVisible(false);
// a cool animation
setTimeout(() => {
onClose();
}, 300); // 300 ms
}, [onClose]);

if (!visible) {
return null;
}

return (
<div>

</div>
)
}

export default InfoModal;

pages/index.tsx中加入InfoModal

1
2
import InfoModal from "@/components/InfoModal";
<InfoModal visible onClose={() => {}} />

接下来继续丰满InfoModal.tsx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import React, { useCallback, useEffect, useState} from "react";
import { AiOutlineClose } from "react-icons/ai"; // close Button

import PlayButton from "./PlayButton"; // PlayButton
import FavoriteButton from "./FavoriteButton";
import useInfoModal from "@/hooks/useInfoModal";
import useMovie from "@/hooks/useMovie";

interface InfoModalProps {
visible?: boolean;
onClose: any;
};

const InfoModal: React.FC<InfoModalProps> = ({ visible, onClose }) => {
// a state for visible, visible is boolean so !! before it
const [isVisible, setIsVisible] = useState(!!visible);

// fetch moveId
const { movieId } = useInfoModal();
// fetch data from movie
const { data = {} } = useMovie(movieId);

// use Effect
useEffect(() => {
setIsVisible(!!visible); // set visible on every new visible change that we get
}, [visible]); // visible in dependency

const handleClose = useCallback(() => {
setIsVisible(false);
// a cool animation
setTimeout(() => {
onClose();
}, 300); // 300 ms
}, [onClose]);

if (!visible) {
return null;
}

return (
<div
className="
z-50
transition
duration-300
bg-black
bg-opacity-80
flex
justify-center
items-center
overflow-x-hidden
overflow-y-auto
fixed
inset-0
"
>
<div
className="
relative
w-auto
mx-auto
max-w-3xl
rounded-md
overflow-hidden
"
>

<div
className={`
${isVisible ? 'scale-100': 'scale-0'}
transform
duration-300
relative
flex-auto
bg-zinc-900
drop-shadow-md
`}>

<div className="relative h-96">
<video
className="
w-full
brightness-[60%]
object-cover
h-full
"
autoPlay
muted
loop
poster={data?.thumbnailUrl}
src={data?.videoUrl}
></video>
</div>
</div>
</div>
</div>
)
}

export default InfoModal;

产生了如下的效果:
Snipaste_2024-03-05_06-42-52.png

接下来再给上面的黑色方框加上一个关闭按钮,并添加播放按钮和收藏按钮。在InfoModal.tsx中添加以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<div 
className="
cursor-pointer
absolute
top-3
right-3
h-10
w-10
rounded-full
bg-black
bg-opacity-70
flex
items-center
justify-center
"
onClick={() => {}}>
<AiOutlineClose className="text-white" size={20} />
</div>

<div className="
absolute
bottom-[10%]
left-10
">
<p className="text-white text-3xl md:text-4xl h-full lg:text-5xl font-bold mb-8">
{data?.title}
</p>
<div className="flex flex-row gap-4 items-center">
<PlayButton movieId={data?.id} />
<FavoriteButton movieId={data?.id} />
</div>
</div>

最后再加上New字样和电影的各类信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<div className="px-12 py-8">
<p className="text-green-400 font-semibold text-lg">
New
</p>

<p className="text-white text-lg">
{data?.duration}
</p>

<p className="text-white text-lg">
{data?.genre}
</p>

<p className="text-white text-lg">
{data?.description}
</p>
</div>

并加上点击关闭按钮实现关闭页面的功能,即在onClick函数中调用handleClose即可:onClick={handleClose}>

然后在pages/index.tsx中实现对上述模块InfoModal.tsx的触发。

1
2
const { isOpen, closeModal } = useInfoModal(); // use useInfoModal hook to trigger InfoModal 
<InfoModal visible={isOpen} onClose={closeModal} />

现在需要实现在billboard中点击More Info按钮展现上述的Info Modal组件的功能。进入components/Billboard.tsx中,写入以下的代码:

1
2
3
4
5
6
7
const { openModal } = useInfoModal();

const handleOpenModal = useCallback(() => {
openModal(data?.id);
}, [openModal, data?.id]);

onClick={handleOpenModal}

在电影卡片中再插入一个按钮。使得点击该按钮,可以展现影片的详细信息,在components/MovieCard.tsx中加入以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const { openModal } = useInfoModal();

<div
onClick={() => openModal(data?.id)}
className="
cursor-pointer
ml-auto
group/item
w-6
h-6
lg:w-10
lg:h-10
border-white
border-2
rounded-full
flex
justify-center
items-center
transition
hover:border-neutral-300">
<BiChevronDown
size={30}
className="text-white group-hover/item:text-neutral-300"/>
</div>

这样,点击电影卡片上的向下的箭头,就会显示出影片的详细信息。调用我们在本节实现的useInfoModal这个hook即可轻松地实现上述功能。

现在继续修复个人profile中名字始终加载为username的问题。将username改为用户实际的名字。进入components/AccountMenu.tsx中,修改以下的代码:

1
2
3
4
5
const { data } = useCurrentUser();

<p className="text-white text-sm group-hover/item:underline">
{data?.name}
</p>

即可在个人profile中加载出实际的用户名。

Vercel Deployment

可以同时复制并粘贴多行命令,命令行会自动逐一执行这些命令。要想在vercel上部署,要确保没有warning。要解决所有warning,只需要在.eslintrc.json中加入代码:

1
2
3
"rules": {
"@next/next/no-img-element": "off"
}

然后在命令行中输入:npm run lint,即可得到:No ESLint warnings or errors。此时所有warning就都被消去了。

注册vercel时,注意用github账号注册vercel,否则需要将账号绑定到github。进入vercel,点击add new,选中想要导入的github仓库,点击import,在configure project页面添加一些environment variables,即将原本项目中.env文件中的各个环境变量(除去NEXTAUTH_URL外)填入即可。

然后点击deploy即可。部署大概需要两三分钟的时间。部署以后,就可以直接通过域名访问我们的项目的网页。我发现要在本地启动项目,即运行命令:npm run dev,才能实现正常的登录功能。尚不清楚为什么,按理来说部署到云平台后就本地的服务就不需要启动了。

目前该问题依然无法解决,而且似乎部署在vercel上的项目无法正常进行google/github oauth验证登录,尚不明白原因,但不再浪费时间去尝试。至少本项目在本地是能够成功运行的,我将本地的项目回滚到了fix prisma error when deploying的版本。通过链接:http://localhost:33350可以正常进行oauth登录,注册和邮箱密码登录。

尝试在vercel上重新部署本应用,现在发现账号密码登录和github oauth登录都可以正常使用了(不需要在本地启动项目,项目直接在vercel上运行),但google oauth还是无法正常运行,我猜测是账号邮箱重复的问题,可以在数据库中查看并验证我的猜测。实际上应该不是账号邮箱重复的问题,就是哪一步配置不对或者网站抽风,不管了。

链接

110.平衡二叉树
257. 二叉树的所有路径
404.左叶子之和

知识

257. 二叉树的所有路径

404.左叶子之和

初次尝试

110.平衡二叉树

先尝试递归解法。我写下了如下的代码,可以运行成功,但时间复杂度较高:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
// 求最大根节点的最大高度,用后序遍历
int getheight(TreeNode* node)
{
if (node == NULL) return 0;
int left = getheight(node->left);
int right = getheight(node->right);
int res = 1 + max(left, right);
return res;
}

bool isBalanced(TreeNode* root) {
if (root == NULL) return true;

bool left = isBalanced(root->left);
int leftdepth = getheight(root->left);

bool right = isBalanced(root->right);
int rightdepth = getheight(root->right);

bool flag = false;
if (abs(leftdepth - rightdepth) <= 1) flag = true;

// 根节点需要同时满足:左子树为平衡二叉树,右子树也为平衡二叉树,且左右子树高度差<=1
// 整个树才是平衡二叉树
bool res = left && right && flag;
return res;
}
};

接着看卡尔的讲解。

257. 二叉树的所有路径

拿到本题,我毫无办法,直接看卡尔的讲解。

404.左叶子之和

本题我本来想一上来就是层序遍历,但后面发现是左叶子,而非左孩子。叶子节点是没有左右孩子的节点。我产生了一个另外的想法,先前序遍历一遍二叉树,遍历到左节点时判断左节点是否是左叶子节点,是的话则将其加入结果res中,最后返回res即可。我尝试了,但做不出来,看卡尔的讲解。

实现

110.平衡二叉树

平衡二叉树:二叉树中任何一个节点左右子树的高度差不超过1。求高度要用后序遍历。本题可以用递归法,也可以用迭代法,但优先掌握递归法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getHeight(TreeNode* node) // 返回一个节点的高度
{
if (node == NULL) return 0; // 终止条件

// 后序遍历
// 若某节点的左右子树的高度差超过1,说明该子树不再为平衡二叉树,进而说明整个树并非平衡二叉树
// 当发现这样的节点时,就不返回节点的高度,直接返回-1
// 左
int left = getHeight(node->left);
if (left == -1) return -1; // 左子树并非平衡二叉树,则返回-1
// 右
int right = getHeight(node->right);
if (right == -1) return -1; // 右子树并非平衡二叉树,则返回-1

// 中
int res;
if (abs(left - right) > 1) res = -1; // 左右子树相差大于1,则说明该子树为非平衡二叉树,返回-1
else res = 1 + max(left, right); // 计算左右子树的父节点的高度
return res;
}

必须用后序遍历,因为需要先计算左右子树的高度,然后才能进行比较。完整代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
// node为根节点的二叉树是平衡二叉树则返回node的高度,是非平衡二叉树则返回-1
int getheight(TreeNode* node)
{
if (node == NULL) return 0;

int left = getheight(node->left);
if (left == -1) return -1;
int right = getheight(node->right);
if (right == -1) return -1;

int res;
if (abs(left - right) > 1) res = -1;
else res = 1 + max(left, right);
return res;
}
bool isBalanced(TreeNode* root) {
if (getheight(root) == -1) return false;
return true;
}
};

257. 二叉树的所有路径

给定二叉树,返回从根节点到叶子节点的所有路径。求路径需要使用前序遍历。原因:只有前序遍历可以让父节点指向孩子节点,从而输出路径。虽然也可以用迭代法,但推荐使用递归法。回溯和递归是相辅相成、相伴而生的。本题第一次提到回溯。本题的解题过程中有回溯的过程。

为什么会有回溯?假设有以下的二叉树:
img

假设有容器收集路径,收集到路径125,如何弹出2和5,然后再让容器重新收集路径13?回溯的过程:弹出5和2,加入3。
关键代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// path数组用来记录单条路径
// res数组用来存放最终的结果(包含多条路径),是一个数组,数组的每个元素都是一个字符串
void traversal(TreeNode* node, vector<int>& path, vector<string>& res)
{
path.push_back(node->val); // 中:处理过程

// 终止条件
// 左右孩子都为空,说明遍历到了叶子节点,收获结果
if (node->left == NULL && node->right == NULL)
{
res.push_back(path); // 将单条路径的结果放入最终结果中,省略了vector->string和加上->的代码
return;
}

// 单层处理逻辑,用前序遍历:中左右
// 中:处理过程,即添加遍历到的节点,本题的处理过程需要写到终止条件之前
// 因为本题的终止条件是到叶子节点,若中写在终止条件之后,则叶子节点没有被放入path中
// 左
if (node->left)
{
traversal(node->left, path, res);
path.pop_back(); // 回溯,弹出5和2
}
// 右
if (node->right)
{
traversal(node->right, path, res);
path.pop_back(); // 回溯
}
}

完整的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
void traversal(TreeNode* node, vector<int>& path, vector<string>& res)
{
path.push_back(node->val); // 中

// 终止条件
if (node->left == NULL && node->right == NULL)
{
string s;
for (int i = 0; i < path.size() - 1; i ++ )
{
s += to_string(path[i]);
s += "->";
}
s += to_string(path[path.size() - 1]);
res.push_back(s);
return;
}

// 左
if (node->left)
{
traversal(node->left, path, res);
path.pop_back(); // 回溯
}
// 右
if (node->right)
{
traversal(node->right, path, res);
path.pop_back(); // 回溯
}
}

vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> res;

if (root == NULL) return res;
traversal(root, path, res);
return res;
}
};

404.左叶子之和

左叶子的定义:首先必须是叶子节点(叶子节点的左右孩子为空)。同时还必须是父节点的左孩子。

本题和之前的二叉树类题目有不同之处。之前的题目遍历到哪个节点就处理哪个节点,但这题遍历到某个节点时,不能直接处理该节点,因为无法判断该节点是否其父节点的左孩子。这题的思路为遍历到某个节点,若其左孩子不为空,但左孩子的左右孩子为空,那么该节点的左孩子就是左叶子,处理该节点的左孩子即可。

本题用后序遍历比较容易,因为后序遍历是左右中,是一层层向上返回。本题也可使用迭代法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int traversal(TreeNode* node) 
{
// 终止条件1
if (node == NULL) return 0;

// 终止条件2,可不写,不写就会做无用的递归
// 如果当前遍历的节点是叶子节点,那其左叶子也必定是0
if (node->left == NULL && node->right == NULL) return 0;

// 左
int leftNum = traversal(node->left);
// node为左叶子的父节点,左叶子为node->left
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL)
leftNum = node->left->val;

// 右
int rightNum = traversal(node->right);
// 中
int sum = leftNum + rightNum;

return sum;
}

上述代码可以精简。但不建议初学者看。

本题其实用层序遍历也可以解决,关键依然在于对于左叶子的父节点的判断,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int res = 0;
queue<TreeNode*> q;

if (root == NULL) return 0;
q.push(root);

while (q.size())
{
int size = q.size();
while (size -- )
{
TreeNode* node = q.front();
q.pop();
if (node->left && node->left->left == NULL && node->left->right == NULL) res += node->left->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
};

直接把queue改为stack,也可以解决本题。采用queue的写法是层序遍历,而采用stack的写法是普通迭代写法(区别于统一迭代写法)。

心得与备忘录

110.平衡二叉树

  1. 平衡二叉树:二叉树中任何一个节点左右子树的高度差不超过1。求高度要用后序遍历。
  2. 我在初次尝试中的做法较为简单,但没有进行剪枝,意味着即使某些树的子树为非平衡二叉树,依然会继续递归,而不是直接return false。这样导致程序的时间复杂度较高。
  3. 卡尔提供的解法的核心思路在于:node为根节点的二叉树是平衡二叉树则返回node的高度,是非平衡二叉树则返回-1。本解法的时间复杂度较低,原因在于当发现某个子树是非平衡二叉树时,就说明整棵二叉树都是非平衡二叉树,则一路返回-1,相当于做了剪枝的操作。
  4. 本题优先掌握递归法即可,不要求掌握迭代写法。迭代写法代码很长,且因为迭代法有很多重复的计算,导致效率很低。

257. 二叉树的所有路径

  1. 本题第一次让我接触到了回溯。更具体地说,是第一次在代码中显示地写出了回溯。

  2. 本题虽然是一个easy,但对我这个初学者来说难度不小,需要记得复习。

  3. 本题的核心思路依然是递归三部曲:

    • 确定传入的参数:节点、单条路径和最终结果,后两者需要加上引用。
    • 终止条件:到达叶子节点
    • 单层递归逻辑:前序遍历。中节点的处理逻辑需要放在终止条件之前,否则单条路径中不包含叶子节点。左右节点的处理逻辑注意判空和回溯。
  4. 本题推荐采用我在实现中的写法,虽然代码略显复杂,但清楚地体现了回溯的过程,且不容易出错。不建议写精简的写法,容易出错,且对理解本题的原理并无帮助。

404.左叶子之和

  1. 注意本题中对于左叶子的定义。
  2. 本题不能遍历到哪个节点就处理哪个节点,而是遍历到左叶子的父节点,就处理左叶子。
  3. 本题采用后序遍历的写法,代码较为简单,结果从下往上一层层返回。本题也可采用层序遍历的套路写法。
  4. 本题有两个终止条件,第二个终止条件可以不写,但会导致多递归一层。
  5. 注意如何判断一个节点是否为左叶子的父节点if (node->left != NULL && node->left->left == NULL && node->left->right == NULL)
  6. 本题依然可以方便地套用层序遍历的常规代码。
  7. 我非常惊讶地发现,在本题中,若采用类似层序遍历的写法,用栈或者队列作为存放遍历过的节点的数据结构,都可以得到能够正常运行的代码。卡尔的讲义上给出的迭代法的写法并非是严格意义上的层序遍历,而仅仅是前序遍历的普通迭代写法(也并非统一迭代)。层序遍历需要用队列作为数据结构,而卡尔给的迭代写法采用了栈作为数据结构,但采用严格的层序遍历的写法依然可以解决这道题。

链接

104.二叉树的最大深度
111.二叉树的最小深度
222.完全二叉树的节点个数

知识

104.二叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

初次尝试

104.二叉树的最大深度

我看到本题后,发现本题在层序遍历里面做过,就用层序遍历先求解。写出了如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> q;

if (root != NULL) q.push(root);
int res = 0;
while (q.size())
{
int size = q.size();
while (size -- )
{
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res ++ ;
}
return res;
}
};

本题应该可以尝试用别的遍历方法,比如递归去求解。直接看卡尔的视频讲解吧。

559. n叉树的最大深度

本题我首先尝试用层序遍历的解法求解,写出了如下的可以AC的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int maxDepth(Node* root) {
queue<Node*> q;
int height = 0;

if (root != NULL) q.push(root);

while (q.size())
{
int size = q.size();
while (size -- )
{
Node* node = q.front();
q.pop();

for (int i = 0; i < node->children.size(); i ++ )
if (node->children[i]) q.push(node->children[i]);
}
height ++ ;
}
return height;
}
};

接着思考如何递归求解。递归知道思路,但写不出取孩子树最大高度的那部分关键代码。

111.二叉树的最小深度

本题可以用层序遍历来做,属于层序遍历的10道题之一。我写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*> q;
int depth = 0;

if (root != NULL) q.push(root);

while (q.size())
{
int size = q.size();
depth ++ ;
while (size -- )
{
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
if (!node->left && !node->right) return depth;
}
}
return depth;
}
};

我再尝试用递归求解。发现有坑,做不出来,看卡尔的讲解。

222.完全二叉树的节点个数

拿到本题,我的第一想法依然是层序遍历。不得不说层序遍历法可以解决很多问题。我写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> q;

if (root != NULL) q.push(root);

int cnt = 0;

while (q.size())
{
int size = q.size();
while (size -- )
{
TreeNode* node = q.front();
q.pop();
cnt ++ ;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return cnt;
}
};

感叹下,层序遍历确实能解决很多题,应该还不止卡尔给出的那10道题。我再来尝试递归解法。我觉得应该采用后序遍历,先统计根节点左右子树的节点数量,将二者加起来再加1即可。我写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;

// 后序遍历:左右中
int left = countNodes(root->left);
int right = countNodes(root->right);
int cnt = left + right + 1;
return cnt;
}
};

这道题我能想到的解法就是这两种,接着看卡尔的讲解。

实现

104.二叉树的最大深度

什么是深度,什么是高度?

  • 深度:二叉树中任意一个节点到根节点的距离。根节点的深度规定为1(0也可以,规则不同)。
  • 高度:二叉树中任意一个节点到叶子节点的距离。叶子节点的高度规定为1。

求高度用后序遍历,求深度用前序遍历。求高度是从下往上计数,因此要求从下往上遍历,而后序遍历顺序为左右中,恰好就是从下往上。求深度是从上往下计数,因此要求从上往下遍历,而前序遍历顺序为中左右。恰好就是从上往下。本题本来应该用前序遍历,但根节点的高度就是二叉树的最大深度因此本题用后序遍历也可以做

递归三部曲:

  • 传入的参数和返回值

    1
    int getheight(TreeNode* node)
  • 终止条件

    1
    if (node == NULL) return 0; // 叶子节点的高度是1,其下的空节点高度是0
  • 单层递归(后序遍历:左右中)

    1
    2
    3
    4
    int leftheight = getheight(node->left); // 左节点高度
    int rightheight = getheight(node->right); // 右节点高度
    int height = 1 + max(leftheight, rightheight); // 中节点高度,为左右孩子的高度取最大值+1
    return height; // 根节点的高度就是二叉树的最大深度

本题的前序遍历写法相比于后序遍历写法要复杂很多(前序遍历还涉及到回溯的过程)。本题也可以用迭代法实现。

559. n叉树的最大深度

受到代码随想录的启发,写出了递归法(类似后序遍历)的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxDepth(Node* root) {
if (root == NULL) return 0; // 终止条件

// 挑选出最高的孩子节点,将其高度记为height
int height = 0;
for (int i = 0; i < root->children.size(); i ++ )
height = max(height, maxDepth(root->children[i]));
height ++ ; // 中节点(父节点)的高度在最高的孩子节点的基础上+1

return height;
}
};

111.二叉树的最小深度

本题和二叉树的最大深度有很多细节不同,容易踩坑。最小深度:根节点到叶子节点的最小距离(根节点到最近的叶子节点的距离)。像104题一样,本题求二叉树的最小深度,也可以通过后序遍历求高度的方式来求解。二叉树的最小深度实际上就是根节点的最小高度。本题求深度,本来应该用前序遍历,但前序遍历的代码不如后序遍历简洁,因此本题依然推荐使用后序遍历

误区,不能写:int height = 1 + min(left, right);,若根节点的左子树为空,右子树不为空,则这样写二叉树的最小深度为1,显然不对。正确的方法是取右子树的最小高度,然后+1。为处理这种情况,需要写如下的单次递归的代码:

1
2
3
4
5
6
7
8
9
10
11
int left = getheight(node->left);
int right = getheight(node->right);
// 若根节点的左子树为空,右子树不为空,二叉树的最小深度为右子树的最小高度+1
if (node->left == NULL && node->right != NULL)
return 1 + right;
// 若根节点的左子树不为空,右子树为空,二叉树的最小深度为左子树的最小高度+1
if (node->left != NULL && node->right == NULL)
return 1 + left;
// 若左右子树都不为空,则取其中最小的最小高度+1返回
int res = 1 + min(left, right);
return res;

本题后序遍历的完整写法如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 后序遍历
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;

int left = minDepth(root->left);
int right = minDepth(root->right);

// 左子树为空,右子树非空
// 也可写作if (left == 0 && right)
if (root->left == NULL && root->right != NULL)
return 1 + right;
// 左子树非空,右子树为空
// 也可写作if (left && right == 0)
if (root->left != NULL && root->right == NULL)
return 1 + left;
// 左右子树都不为空
int res = 1 + min(left, right);
return res;
}
};

我写出了一个精简后的版本,但并不会影响代码的可读性(依然可以轻松看出后序遍历):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;

int left = minDepth(root->left); // 左
int right = minDepth(root->right); // 右

// 中
if (!left && right) return 1 + right; // 左空右不空
if (left && !right) return 1 + left; // 左不空右空
return 1 + min(left, right); // 左右都不空
}
};

222.完全二叉树的节点个数

普通二叉树,递归法(前中后序)和迭代法(层序遍历)都可以求二叉树的节点个数。我在初次尝试中写的两个版本的代码都是把本题中的二叉树当成了普通二叉树,而没有利用完全二叉树的特性。本题强调了完全二叉树,就是暗示我们尽量利用完全二叉树的特性。

在递归法(前中后序)中,后序遍历的代码是最简洁的。每个节点都遍历了一遍,时间复杂度是O(n)。接下来利用完全二叉树的特性来降低时间复杂度。完全二叉树:除了底层节点,上面的节点都是满的。底层节点从左到右依次排开。对于满二叉树,只要知道深度h,节点数目就是2^h - 1。对于完全二叉树,如果其子树是满二叉树,则可以直接用上述公式来计算,计算完左右子树的节点数再+1(根节点)即可。关键:如何判断子树为满二叉树,并求其深度

对于满二叉树,一直向左遍历和一直向右遍历的深度应该是相等的。一直向左遍历和一直向右遍历的深度相等的完全二叉树的子树一定是满二叉树若遇到子树非满二叉树的情况,则继续向下遍历(即继续遍历子树的左右子树),直到是满二叉树为止,然后不断返回并+1。这种方式利用了完全二叉树的特性,且避免了遍历没有必要的节点,时间复杂度小于O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int getNum(TreeNode* node)
{
// 终止条件1
if (node == NULL) return 0;

// 终止条件2:遇到子树为满二叉树的情况,则返回子树中节点的数量
TreeNode* left = node->left; // 用于遍历子树的左侧
TreeNode* right = node->right; // 用于遍历子树的右侧
int leftdepth = 0, rightdepth = 0; // 左侧和右侧的深度
// 计算左侧的深度
while (left)
{
left = left->left;
leftdepth ++ ;
}
// 计算右侧的深度
while (right)
{
right = right->right;
rightdepth ++ ;
}
// 左右侧深度相等,说明子树是满二叉树,可以利用公式快速计算子树的节点数量
if (leftdepth == rightdepth) return (2 << leftdepth) - 1; // 2 << 0 = 2^1, 2 << 1 = 2^2

// 单层递归的逻辑,后序遍历
leftnum = getNum(node->left); // 左子树数量
rightnum = getNum(node->right); // 右子树数量
int res = leftnum + rightnum + 1; // 中
return res;
}

上述解法不需要去遍历完全二叉树中的所有节点,而是用公式直接计算子树为满二叉树时的节点数量并返回。

心得与备忘录

104.二叉树的最大深度

  1. 本题可以用层序遍历法求解,属于层序遍历法可以求解的10道题之一。但本题用递归(后序遍历)求解代码最为简洁。
  2. 注意二叉树中深度和高度这两个概念。某个节点的深度指其到根节点的距离,某个节点的高度指其到叶子节点的距离。这两个概念可以说是相反的。
  3. 求深度用前序遍历,求高度用后序遍历。
  4. 二叉树的最大深度就是根节点的高度。因此本题可以用后序遍历求解,实际上后序遍历的代码远比前序遍历的代码简单。因此本题的推荐做法就是后序遍历。
  5. 对于559. n叉树的最大深度。同样可以采用类似后序遍历的递归方法和层序遍历的迭代方法。对于递归方法,注意如何挑选出最高的孩子节点。

111.二叉树的最小深度

  1. 本题可以用迭代法(层序遍历)和递归法(前/后序遍历)求解。最推荐的方法是后序遍历,因为其代码最为简洁。
  2. 后序遍历是用来求高度的,但二叉树的最小深度就是根节点的最小高度,因此本题可以用后序遍历。
  3. 本题的易错点为:不可以直接将104题的max改成min(因为二叉树的最小深度为根节点到叶子节点的最小距离),而是要针对左右子树是否为空进行分类讨论。
  4. 本题的层序遍历写法同样需要注意:只有当左右孩子都为空的时候,才说明遍历到最低点了。

222.完全二叉树的节点个数

  1. 本题可以采用递归写法和迭代写法。递归写法建议采用后序遍历,迭代写法建议采用层序遍历。二者的时间复杂度都是O(n)。
  2. 上述方法对普通二叉树都适用,但对本题的完全二叉树,充分利用其特性可将时间复杂度进一步减小。
  3. 一直向左遍历和一直向右遍历的深度相等的完全二叉树的子树一定是满二叉树若遇到子树非满二叉树的情况,则继续向下遍历,最终必然会遇到满二叉树。对于满二叉树,只要知道深度h,节点数目就是2^h - 1。因此不需要遍历完全二叉树的每一个节点,就可以求得其节点的个数。
  4. 上述解法的终止条件有两个,一个是遇到叶子节点,另一个是子树为满二叉树。单层递归逻辑采用后序遍历写法。
  5. 时间复杂度分析:递归调用的次数=树的高度=log n,每层递归需要计算子树的高度,故也是log n。因此总的时间复杂度为O(log n * log n)。
  6. 空间复杂度分析:递归的深度(即递归调用栈的最大深度)大约是树的高度。对于一棵平衡二叉树来说,其高度大约是log n,其中n是树中节点的数量。故空间复杂度为O(log n)。

链接

层序遍历
226.翻转二叉树
101. 对称二叉树

知识

层序遍历

二叉树的层序遍历相当于图论中的广度优先搜索。leetcode 102:层序输出二叉树。

1
2
3
4
5
6
7
graph TD;
A[6] --> B[4];
A --> C[7];
B --> D[1];
B --> E[3];
C --> F[5]
C --> G[8]

上述二叉树,一层放在一个数组里,返回的是二维数组。只依赖二叉树本身的结构,无法层序保存二叉树中的节点。需要借助另一种数据结构:队列,用于保存每一层遍历过的元素。图论中的广度优先搜索也是依赖队列实现的。

模拟过程:根节点6加入队列,记录队列大小(size=1)。size表示这层二叉树中有几个元素。接下来弹出当前层的元素6,将6加入到结果数组中,开始处理下一层。再将6的左右孩子4和7加入队列中,此时size=2,第二层的元素个数为2,接下来弹出size(2)个元素,先弹出4,将4的左右孩子1和3加入队列。再弹出7,size归0,第二层遍历结束。弹出7后,再将7的左右孩子5和8加入队列。此时size=4,说明第三层中元素个数为4。接着队列中再弹出size(4)个元素,加入结果数组。上述过程如下图所示。
Snipaste_2024-02-16_02-48-16.png

我尝试根据上述模拟过程独立写出代码,但不知道怎么写while循环结束的条件。直接看卡尔的讲解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> res;
queue<TreeNode*> q;
if (root != NULL) q.push(root);

// 遍历的终止条件:队列中无元素
while (q.size())
{
int size = q.size(); // 记录当前层节点的数量
vector<int> vec; // 存放一层的节点的值
// 队列中弹出size个节点,加入到vec中
while (size -- )
{
TreeNode* node = q.front();
q.pop();
vec.push_back(node->val);

// 将弹出节点的左右孩子加入到队列中
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(vec);
}
return res;

上述代码也是图论中广度优先搜索的模板。leetcode上有10道题都可以用本模板解决,只需要改动不超过三行代码。

初次尝试

226.翻转二叉树

我能想到的办法是层序遍历二叉树,然后将每一层的输出数组翻转。但这样做需要将数组还原回到二叉树,比较麻烦。随后有产生想法,让一个节点的左指针指向其右节点,右指针指向其左节点即可,可能需要一个中间变量来存放左节点或者右节点。直接看卡尔的视频。

101. 对称二叉树

看到本题,我的第一想法是,本题是翻转二叉树的变式。若一个二叉树被翻转后,仍和原来保持一致,那么就可以认为它是对称二叉树。现在的问题在于如何比较两棵二叉树是否完全相同,我认为可以采用层序遍历,一层层比较即可。或者直接层序遍历完后将二叉树存入一个二维数组中,然后用两重循环+双指针算法判断二维数组是否对称。这样做实际上有个问题:

img

上面这棵二叉树,层序遍历得到的二维数组为[1, [2, 2], [3, 3]]。二维数组是对称的,但二叉树却不是对称的。还是看卡尔的讲解吧。

实现

层序遍历

107.二叉树的层次遍历II

只需要在最后翻转res数组即可:reverse(res.begin(), res.end());。翻转一个二维数组,二维数组中所有元素(一维数组)的顺序都会颠倒,但一维数组本身(即一维数组内部的顺序不会改变)。reverse函数可以用双指针算法手动实现:

1
2
3
int len = res.size();
for (int i = 0, j = len - 1; i < len / 2; i ++ , j -- )
swap(res[i], res[j]);

似乎手动实现的速度要快于调用现成的reverse函数。

199.二叉树的右视图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;

if (root != NULL) q.push(root);
while (q.size())
{
int size = q.size();
for (int i = 0; i < size; i ++ )
{
TreeNode* node = q.front();
q.pop();
if (i == size - 1) res.push_back(node->val); // 将一层最右边的节点的值加入到结果数组中
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
};

637.二叉树的层平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
queue<TreeNode*> q;

if (root != NULL) q.push(root);
while (q.size())
{
int size = q.size();
double sum = 0;
for (int i = 0; i < size; i ++ )
{
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(sum / size);
}
return res;
}
};

429. N叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> q;

if (root != NULL) q.push(root);
while (q.size())
{
vector<int> vec;
int size = q.size();

while (size -- )
{
Node* node = q.front();
q.pop();
vec.push_back(node->val);
for (int i = 0; i < node->children.size(); i ++ )
if (node->children[i]) q.push(node->children[i]);
}
res.push_back(vec);
}
return res;
}
};

515.在每个树行中找最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;

if (root != NULL) q.push(root);
while(q.size())
{
int size = q.size();
int max = -2147483648; // Node.val的最小值,可简写为int max = INT_MIN;
while (size -- )
{
TreeNode* node = q.front();
q.pop();
max = node->val > max ? node->val: max; // 注意问号表达式的用法
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(max);
}
return res;
}
};

116. 填充每个节点的下一个右侧节点指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> q;

if (root != NULL) q.push(root);
while (q.size())
{
int size = q.size();
Node* node0, *node;
for (int i = 0; i < size; i ++ )
{
// 取出一层的头结点
if (i == 0)
{
node0 = q.front();
q.pop();
// 本句话的目的:当一层只有头节点时,可以让该头节点在弹出的同时继续在队列中行插入其左右子节点
node = node0;
}
// 本层前一个节点next指向本节点
else
{
// node0和node交替前进
node = q.front();
q.pop();
node0->next = node;
node0 = node;
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
// 本层最后一个节点指向NULL
node->next = NULL;
}
return root;
}
};

117.填充每个节点的下一个右侧节点指针II

本题代码和116完全相同。116题目中的条件:完整二叉树实际上是多余的。不管是不是完整二叉树,都可以用同样的代码解题。

104.二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxDepth(TreeNode* root) {
int res = 0;
queue<TreeNode*> q;

if (root != NULL) q.push(root);
while (q.size())
{
int size = q.size();
while (size -- )
{
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res ++ ;
}
return res;
}
};

111.二叉树的最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int minDepth(TreeNode* root) {
int res = 0;
queue<TreeNode*> q;

if (root != NULL) q.push(root);
while (q.size())
{
int size = q.size();
bool flag = true;
while (size -- )
{
TreeNode* node = q.front();
q.pop();
if (node->left == NULL && node->right == NULL)
{
flag = false;
break;
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res ++ ;
if (flag == false) break;
}
return res;
}
};

注意:只有当某个节点的左右孩子都为空,这个节点才在二叉树的底部。一旦遇到这样的节点,立即跳出循环,返回res。根据这个思路,我将上述代码做了简化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int minDepth(TreeNode* root) {
int res = 0;
queue<TreeNode*> q;

if (root != NULL) q.push(root);
while (q.size())
{
int size = q.size();
while (size -- )
{
TreeNode* node = q.front();
q.pop();
if (node->left == NULL && node->right == NULL)
return ++ res;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res ++ ;
}
return res;
}
};

226.翻转二叉树

面试中的常考题。本质是交换每个节点的左右孩子,交换的是指针而非数值。这道题显然用递归解比较简单,但要想清楚用哪种遍历顺序。本题用前序和后序是最直接的,用中序遍历代码比较难写。迭代和层序遍历也可以做此题,但不要求掌握。

递归三部曲:

  • 确定递归函数的返回值和参数: TreeNode* invertTree(root)

  • 确定函数的终止条件:if (root == NULL) return root

  • 具体的处理逻辑:前序遍历——中左右

    对中节点,需要交换中节点的左右孩子: swap(root->left, root->right)

    左节点:invertTree(root->left);

    右节点:invertTree(root->right);

    将swap函数放在处理逻辑的最后,就是左右中,就是后续遍历。因此前序和后续遍历皆可解本题。但中序遍历不可以,举个例子:

    1
    2
    3
    4
    5
    6
    7
    graph TD;
    A[4] --> B[2];
    A --> C[7];
    B --> D[1];
    B --> E[3];
    C --> F[6]
    C --> G[9]
    1
    2
    3
    4
    5
    6
    7
    graph TD;
    A[4] --> B[2];
    A --> C[7];
    B --> D[3];
    B --> E[1];
    C --> F[6]
    C --> G[9]
    1
    2
    3
    4
    5
    6
    7
    graph TD;
    A[4] --> B[7];
    A --> C[2];
    B --> D[6];
    B --> E[9];
    C --> F[3]
    C --> G[1]
    1
    2
    3
    4
    5
    6
    7
    graph TD;
    A[4] --> B[7];
    A --> C[2];
    B --> D[6];
    B --> E[9];
    C --> F[1]
    C --> G[3]

    相当于原先根节点的左子树被处理了两次,原先根节点的右子树没被处理。对中序遍历的写法,具体的逻辑应该为:

    1
    2
    3
    invertTree(root->left); // 处理左子树
    swap(root->left, root->right); // 交换左右子树,原先的右子树变为了现在的左子树,原先的左子树变为了现在的右子树
    invertTree(root->left); // 原先的左子树已经被处理过了,现在需要处理原先的右子树,就是现在的左子树

    不建议绕弯子去写中序,很容易出错。

前序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 前序遍历写法
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root; // 终止条件

// 中左右
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root; // 每次递归后返回结果
}
};

后序遍历写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 后序遍历写法
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;

// 左右中
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};

中序遍历写法(绕,理解即可,不要写):

1
2
3
4
5
6
7
8
9
10
11
12
13
// 中序遍历写法
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;

// 左中右
invertTree(root->left);
swap(root->left, root->right);
invertTree(root->left);
return root;
}
};

101. 对称二叉树

本质上是判断根节点的左子树和右子树是否可以互相翻转。需要比较二叉树同是外侧的节点和同是内侧的节点是否相等。接着考虑用哪种方式遍历二叉树。二叉树类的题目确定遍历顺序非常重要本题目只能使用后序遍历(左右中)。因为我们需要先收集完根节点左右孩子的信息再返回给根节点,才能知道根节点的左右孩子是否相同,进而知道二叉树是否是对称的。

  1. 确定函数传入的参数和返回值

    1
    2
    3
    4
    5
    // 判断根节点的左右子树是否可以互相翻转
    // 本质是判断两个二叉树是否可以相互翻转,因此需要同时处理两棵二叉树
    bool compare(TreeNode* left, TreeNode* right) // 传入的参数为左子树的头节点和右子树的头节点
    {
    }
  2. 确定终止条件
    共有以下5种情况
    |左节点|右节点|返回值|
    |:—-:|:—-:|:—-:|
    |空|非空|false|
    |非空|空|false|
    |空|空|true|
    |非空且值不等|非空且值不等|false|
    |非空且值相等|非空且值相等|继续向下遍历,写单层递归的逻辑|

    1
    2
    3
    4
    if (left == NULL && right != NULL) return false;
    else if (left != NULL && right == NULL) return false;
    else if (left == NULL && right == NULL) return true;
    else if (left->val != right->val) return false;
  3. 单层递归的逻辑(如何像下一层遍历)
    同是外侧的节点和同是内侧的节点相同,才可以return true。

    1
    2
    3
    4
    bool outside = compare(left->left, right->right); // 比较一对外侧节点是否相同
    bool inside = compare(left->right, right->left); // 比较一对内侧节点是否相同
    bool res = outside && inside; // 内外侧节点都相同,则才可以左右翻转
    return res;

    上面代码框的前三行代码分别对应后序遍历的左右中。中只能放在最后,不能提前,否则会出现还没计算outside和inside就来计算res的情况,因此必须是后序遍历。

后序遍历解决本题的完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right)
{
if (left == NULL && right == NULL) return true;
else if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left->val != right->val) return false;

bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
bool res = outside && inside;
return res;
}

bool isSymmetric(TreeNode* root) {
return compare(root->left, root->right);
}
};

本题也可以用迭代法实现。

572.另一个树的子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right)
{
if (left == NULL && right == NULL) return true;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right != NULL) return false;
else if (left->val != right->val) return false;

bool outside = compare(left->left, right->left);
bool inside = compare(left->right, right->right);
bool res = outside && inside;
return res;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (subRoot == NULL) return true;
else if (root == NULL) return false;
else if (compare(root, subRoot)) return true;
// 递归比较root树的子树和subRoot是否相同
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};

本题注意如何递归地比较root树的子树和subRoot树是否相同:return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);

心得与备忘录

层序遍历

  1. 本题(leetcode102)的模板需要熟记,可以用来解决10道leetcode。
  2. 本题的关键在于用队列来保存每一层遍历过的元素。
  3. 本题的思路可以概括为:将二叉树的一层加入到队列中,记录队列的大小为size。然后弹出size个节点,用数组收集弹出的节点,并在弹出节点的同时插入弹出的节点的左右子节点。弹完size个节点后,数组中就是当前层的所有元素,而队列中则是下一层的所有节点。
  4. 本题不需要用指针来遍历整棵树,只需要对维护和操作队列即可。
  5. 本题收获最终结果的退出条件为队列为空;二叉树的一层遍历完毕的退出条件为size = 0。
  6. 二叉树的右视图这题需要特别注意,以下写法是错误的:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
    vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    queue<TreeNode*> q;

    if (root != NULL) q.push(root);
    while (q.size())
    {
    int size = q.size();
    while (size -- )
    {
    TreeNode* node = q.front();
    q.pop();
    res.push_back(node->val);
    if (node->right) q.push(node->right);
    }
    }
    return res;
    }
    };

    原因是:对于以下的二叉树:

    1
    2
    3
    graph TD;
    A[6] --> B[4];
    A --> C[NULL];

    尽管6只有左子节点,没有右子节点,但站在二叉树的右边看这颗二叉树,看到的结果是[6, 4],如果按照上面的写法,则返回的结果是[6],4作为左子节点不会被加入到队列中,也不会出现在结果数组中。

  7. N叉树的层序遍历需要注意:新定义的N叉树的名字叫Node,不要下意识地写成TreeNode。在队列中更新N叉树下一层的节点时,注意需要用for循环遍历一遍当前node的孩子数组,因为N叉树中的一个节点不仅有左右孩子,而是有一个孩子数组。

  8. 二叉树的最大深度的解题关键在于:层序遍历二叉树,每遍历完一层记录层数的变量+1。

  9. 二叉树的最大/最小深度这两道题,res ++放在第二重while循环之后和之前都可以。我在实现中的写法都是把res ++放在了第二重while循环之后,但实际上放在第二重while循环之前写出的代码更简洁易懂,可以参考代码随想录上给出的代码。

  10. 注意复习填充每个节点的下一个右侧节点指针,这道题第一遍没有写出来。本题的关键在于特判一层的头节点,以及node0和node交替前进。

  11. 116和117题的代码完全相同。差别只在于116题题目说是完整二叉树,117题目则没有这个说明。

226.翻转二叉树

  1. 注意:本题中的root是指遍历的每个节点,而非特指根节点。

  2. 本题的关键思路:交换中节点的左右子树,递归处理左右节点。

  3. 记住前序和后续的写法即可,swap要么写在左右的上面,要么写在左右的下面。抛弃中序写法,太绕!

  4. 记得最后要return root。因为终止条件:if (root == NULL) return root,只会返回一个为空的节点。大多数情况下不会触发这个终止条件,而是触发最后一个return root

  5. 可以定义一个cur节点遍历二叉树的每个节点,这样就不会与根节点root产生混淆。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // 前序遍历写法
    class Solution {
    public:
    TreeNode* invertTree(TreeNode* root) {
    TreeNode* cur = root;
    if (cur == NULL) return cur;

    // 中左右
    swap(cur->left, cur->right);
    invertTree(cur->left);
    invertTree(cur->right);
    return cur;
    }
    };
  6. 本题除递归写法外,用一般迭代、统一迭代、层序遍历的写法都可以,其实在原本的三种迭代方式的代码的基础上稍作修改就可以,但三种迭代方式的代码本身就已经较为复杂,容易写错,因此除非必须建议不要采用迭代写法。

  7. 但还是不得不说,层序遍历解本题也很方便,本题也可以归类到层序遍历能够解决的10道题中,在层序遍历的基础上,交换每个节点的左右子节点即可,代码如下所示:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
    TreeNode* invertTree(TreeNode* root) {
    queue<TreeNode*> q;

    if (root != NULL) q.push(root);
    while (q.size())
    {
    int size = q.size();
    while (size -- )
    {
    TreeNode* node = q.front();
    q.pop();
    swap(node->left, node->right); // 交换每个节点的左右子节点
    if (node->left) q.push(node->left);
    if (node->right) q.push(node->right);
    }
    }
    return root;
    }
    };

101. 对称二叉树

  1. 本题实际上需要比较根节点的左右子树是否可以相互翻转,因此需要同时遍历两棵树,所以传入的参数为左右子树的头节点。
  2. 本题只能采用后序遍历,遍历左子树的顺序是左右中,遍历右子树的顺序是右左中。
  3. 终止条件需要分五类讨论。见实现中的表格。
  4. 单层递归的核心逻辑为:判断同在外侧的节点是否相同,判断同在内侧的节点是否相同。
  5. 本题的迭代写法其实也不难理解,原理是通过一个容器来成对的存放我们要比较的元素。但优先掌握本题的递归写法即可。
  6. 100.相同的树和572.另一个树的子树基本和本题是一样的,只要稍加修改就可以。572题稍有特殊,需要注意如何递归地比较root树的子树和subRoot树是否相同。同时在主函数中也需要进行分类讨论(subRoot树为空, root树为空,两树相同,root树的子树和subRoot树相同/相异)。

链接

理论基础
递归遍历
迭代遍历
统一迭代

知识

理论基础

二叉树的种类

解题过程中二叉树有两种主要的形式:满二叉树和完全二叉树(完全二叉树包含满二叉树,满二叉树一定是完全二叉树)

“度”是指一个节点拥有的子节点的数量

满二叉树

满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。也可以说深度为k,有2^k-1个节点的二叉树。

完全二叉树

完全二叉树:除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。

之前我们刚刚讲过优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的树,都是没有数值的,而二叉搜索树是有数值的了,二叉搜索树是一个有序树。搜索的时间复杂度是O(logn)。

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树
    平衡二叉树
    平衡二叉树(Balanced Binary Tree)是一种特殊的二叉树,它满足以下性质:对于树中的每一个节点,其左子树和右子树的高度差的绝对值不超过1。这个条件确保了树的高度大致保持在log(n)级别,其中n是树中节点的数量。由于这种高度平衡,平衡二叉树可以在对数据进行插入、删除和查找操作时提供较好的性能,特别是保持操作的时间复杂度接近于O(logn)
    平衡二叉搜索树
    平衡二叉搜索树:又被称为AVL树。具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn。map的key和set中的元素是有序的,因为它们的底层实现是平衡二叉搜索树,而平衡二叉搜索树是有序的。

二叉树的存储方式

二叉树可以链式存储,也可以顺序(线性)存储。那么链式存储方式就用指针, 顺序存储的方式就是用数组。顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。

用数组来存储二叉树如何遍历的呢?如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。但是用链式表示的二叉树,更有利于我们理解,所以一般我们都是用链式存储二叉树

代码构造二叉树:创造一个头节点,其左指针指向左子节点,右指针指向右子节点,然后向函数中传入头节点即可。

二叉树的遍历方式

二叉树主要有两种遍历方式:

  1. 深度优先遍历:先往深走,遇到叶子节点再往回走。
  2. 广度优先遍历:一层一层的去遍历。

从深度优先遍历和广度优先遍历进一步拓展,才有如下遍历方式:

  1. 深度优先遍历(一般用递归法)
  • 前序遍历(递归法,迭代法)
  • 中序遍历(递归法,迭代法)
  • 后序遍历(递归法,迭代法)
  1. 广度优先遍历
    层次遍历(迭代法)

这里前中后,其实指的就是中间节点的遍历顺序(但是所有遍历顺序都是先左后右)。
左指左子树,右指右子树。在左右子树中继续按照规则搜索。
前序遍历:中左右
中序遍历:左中右
后序遍历:左右中

img

每个子树和整棵树都遵循中左右/左中右/左右中。

最后再说一说二叉树中深度优先和广度优先遍历实现方式,我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。之前我们讲栈与队列的时候,就说过栈其实就是递归的一种实现结构,也就说前中后序遍历的逻辑其实都是可以借助使用递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现,这也是队列先进先出的特点所决定的,因为需要先进先出的结构,才能一层一层的来遍历二叉树。

二叉树的定义

链式存储的二叉树节点的定义方式:

1
2
3
4
5
6
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

二叉树的定义和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针,有两个指针,指向左右孩子。

递归遍历

针对leetcode上的三道题目,分别是前序、中序、后序遍历,题号是144,145和94。按照三步来思考,才能保证写出正确的递归代码。所有二叉树的题目都用递归三部曲进行分析。本章节主要讲如何写出递归的代码,不关注底层实现机制。

三部曲:

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑

前序遍历

前序:中左右

  1. 确定递归函数的参数和返回值

    没必要一次性确定,可以在写递归函数时根据需要来填充参数。一般参数为根节点和数组,后者用来存放遍历的结果。返回值一般是void,因为我们把想要的结果放在了参数的数组中。

    1
    2
    3
    4
    void traversal(TreeNode* cur, vector<int>& vec) // 参数为根节点和结果数组
    {

    }
  2. 确定终止条件(搞不好会出现栈溢出等问题)。深度优先搜索是遇到NULL时返回。

    1
    2
    if (cur == NULL)
    return;
  3. 确定单层递归的逻辑

    1
    2
    3
    vec.push_back(cur->val); // 中
    treversal(cur->left, vec); // 左
    treversal(cur->right, vec); // 右

    注意在前序遍历中上面三行代码的顺序不可改变。

中序遍历

左中右。只需要改变第三步:确定单层递归的逻辑的代码。三行代码的顺序不可改变。

1
2
3
treversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
treversal(cur->right, vec); // 右

后序遍历

左右中。同样只需要改变第三步:确定单层递归的逻辑的代码。三行代码的顺序不可改变。

1
2
3
treversal(cur->left, vec); // 左
treversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中

迭代遍历

前序遍历

非递归的方式:迭代法,如何实现二叉树的前中后序遍历。通常对简单的递归逻辑,要求写出相应的迭代(非递归)写法。最基础的就是用迭代法实现前中后序遍历。使用迭代法模拟递归,也需要使用到栈这种数据结构。理论上,所有递归都可以用栈模拟出来。

以下面的二叉树为例。

1
2
3
4
5
graph TD;
A[5] --> B[4];
A --> C[6];
B --> D[2];
B --> E[1];

前序遍历上述二叉树,顺序为中左右,输出结果为54216。用栈来辅助遍历上述二叉树。首先将5加入栈中,然后弹出5,将其放入结果数组中。接着处理5的左右孩子,先把6加入栈中,再把4加入栈中(栈是先进后出的),然后弹出4,将其放入结果数组中。接着处理4的左右孩子,依旧是先放右孩子1,再放左孩子2,然后弹出2,加入结果数组中,因为2已经是叶子节点了,接着弹出1,加入结果数组中,最后弹出6,加入结果数组中。结果数组中是54216,符合预期。关键点是先将右孩子放入栈中,再将左孩子放入栈中,这样弹出时就会先弹出左孩子。弹出时还要关注弹出的节点是否是叶子节点。是,则不需要继续向栈中加入元素;否,则需要向栈中继续加入弹出节点的左右孩子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> function(TreeNode* root)
{
stack<TreeNode*> st; // 栈
vector<int> res; // 结果数组

st.push(root); // 中节点入栈
// 栈不为空,则执行以下逻辑
while (!st.empty())
{
// 将中节点从栈中弹出,加入到结果数组中
TreeNode* node = st.top();
st.pop();
if (node != NULL) // 特判:中节点是否为空
res.push_back(node->val);
else continue; // 若中节点为空,进入下一次循环

// 将中节点的左右孩子放入栈中,先将右孩子入栈,再将左孩子入栈,这样出栈时才是先左后右的顺序
st.push(node->right); // 右
st.push(node->left); // 左
}
return res;
}

递归模拟前序遍历,本来前序遍历的顺序应该是中左右,但由于栈先进后出的特性,代码中实际的顺序是中右左。

后序遍历

后序遍历是左右中。实现后序遍历的原理如下图所示:

1
2
3
graph LR
A[前序遍历:中左右] -->|颠倒左右| B[中右左]
B -->|翻转结果数组| C[左右中]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> function(TreeNode* root)
{
stack<TreeNode*> st;
vector<int> res;

st.push(root);
while (!st.empty())
{
// 中
TreeNode* node = st.top();
st.pop();
if (node != NULL)
res.push_back(node->val);
else continue;

st.push(root->left); // 左
st.push(root->right); // 右
}
reverse(res.begin(), res.end());
return res;
}

中序遍历

中序遍历无法在前序遍历的基础上通过交换某几行代码的顺序来实现。遍历节点和处理节点是两种逻辑。前序和后序遍历中,遍历的节点和要处理的节点是一个顺序,才能写出上述比较简洁的代码。但在中序遍历中,遍历节点的顺序与和处理节点的顺序不同。后面会继续介绍中序遍历的写法,以及如何像递归写法那样更改几行代码的顺序来实现前中后序遍历的迭代写法。

处理二叉树时有两步操作,一步是访问节点,一步是处理节点。访问节点是从根节点开始,一个节点一个节点地去访问。处理节点是把访问到的节点中的元素放入结果数组中。

以下面的二叉树为例:

1
2
3
4
5
graph TD;
A[5] --> B[4];
A --> C[6];
B --> D[1];
B --> E[2];

对于中序遍历,先访问的节点是5,但先处理的节点应该是1(先把1放入结果数组中)。我们要处理1节点,需要先访问节点5、4、1。这就造成了访问的顺序和处理的顺序不同。因此中序遍历需要另一套写法。

下面模拟中序遍历迭代法的过程。需要一个指针帮助我们遍历二叉树,同时用栈记录遍历过的顺序,然后逆向输出即可。指针一路向左访问,指针先指向5,5入栈;指针再指向4,4入栈;指针再指向1,1入栈。到叶子节点了(叶子节点的左指针为空),便从栈中取出元素,从栈中弹出1并加入到结果数组中。看1的右孩子,为空,故再从栈中弹出4并加入到结果数组中,看4的右孩子,不为空,4的右孩子2入栈。2的左孩子为空,故将2从栈中弹出,加入到结果数组中。再看2的右孩子,为空,故从栈中弹出5并加入到结果数组中。5的右孩子为6,不为空,6入栈。6的左孩子为空,故6出栈,加入结果数组中。6的右孩子为空,本该从栈中弹出元素,但此时栈为空,故结束。结果数组为14256,符合中序遍历的顺序。

总结:用指针遍历节点,用栈来记录遍历过的节点,再从栈中弹出元素放入结果数组中。指针一路向左访问,若某个节点的左指针为空,则从栈中取出该节点并放入结果数组中。若某个节点的右指针为空,则从栈中弹出顶部元素并放入结果数组中,若某个节点的右指针不为空,则将右指针指向的节点入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<int> traversal(TreeNode* root)
{
vector<int> res;
stack<TreeNode*> st;
TreeNode* cur = root; // 用于遍历二叉树的指针,一开始指向根节点

// cur为空且栈也为空时,遍历终止
while (cur != NULL || !st.empty())
{
// 栈用于记录指针访问过的元素
if (cur != NULL)
{
st.push(cur);
cur = cur->left; // 指针一路向左访问
}
// 指针一路向左,遇到某个节点的左指针为空
// 则从栈中取出该节点并放入结果数组中
else
{
cur = st.top();
st.pop();
res.push_back(cur->val);

// 看当前指针的右孩子是否为空
// 若为空,则从栈中弹出顶部节点,并将其加入到结果数组中
// 若不为空,则将右孩子入栈
cur = cur->right;
}
}
return res;
}

目前迭代法的前中后序遍历没有像递归那样统一起来,其实也是可以统一起来的。统一的写法:用一个栈完成遍历节点和处理节点的过程,但栈中要加入空节点做标记,标记正在遍历的节点和处理的节点。

统一迭代

对前中后序这三种遍历方式,使用迭代法是可以写出统一风格的代码。以中序遍历为例,我们就将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。如何标记呢,就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;

// 根节点非空才将其放入栈中
if (root != NULL) st.push(root);

// 循环条件:栈不为空
while (!st.empty())
{
// 弹出栈顶元素
TreeNode* node = st.top();
st.pop();

// node不为空,则按照右中左的顺序访问节点
if (node != NULL)
{
if (node->right) st.push(node->right); // 右节点
st.push(node); // 中节点
st.push(NULL); // 中节点访问过,但是还没有处理,加入空节点做为标记
if (node->left) st.push(node->left); // 左节点
}
// 只有遇到空节点的时候,才处理节点(将下一个节点放进结果集)
else
{
// 将空节点弹出,重新取出栈中的元素
node = st.top();
st.pop();
res.push_back(node->val); // 加入到结果集中
}
}
return res;
}
};

对于前序和后序遍历,只需要改变node不为空时访问节点的顺序即可。前序遍历原本的顺序是中左右,考虑到栈先入后出的特性,调整为右左中。后续遍历原本的顺序是左右中,考虑到栈先入后出的特性,调整为中右左。

实现

递归遍历

144. 前序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
// 前序遍历递归写法的核心函数
void traversal(TreeNode* root, vector<int> &vec) // 递归函数的参数和返回值
{
if (root == NULL) return; // 确定终止条件

vec.push_back(root->val); // 中
traversal(root->left, vec); // 左
traversal(root->right, vec); // 右
}

// 相当于主函数,调用核心函数
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;

traversal(root, res); // 调用核心函数
return res;
}
};

完整的,带有测试样例的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
void traversal(TreeNode* root, vector<int>& res) {
if (root == NULL) return;
res.push_back(root->val);
traversal(root->left, res);
traversal(root->right, res);
}

vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root, res);
return res;
}
};

int main() {
// 构建树的示例代码,需要根据实际情况调整
TreeNode* node3 = new TreeNode(3);
TreeNode* node2 = new TreeNode(2, node3, nullptr);
TreeNode* root = new TreeNode(1, nullptr, node2);

Solution solution;
vector<int> res = solution.preorderTraversal(root);

// 打印结果
for (int val : res) {
cout << val << " ";
}
cout << endl;

// 释放分配的内存(在实际使用中,考虑使用智能指针自动管理内存)
delete node3;
delete node2;
delete root;

return 0;
}

145. 后序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
void traversal(TreeNode* root, vector<int>& res)
{
if (root == NULL) return;

traversal(root->left, res); // 左
traversal(root->right, res); // 右
res.push_back(root->val); // 中
}

vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;

traversal(root, res);
return res;
}
};

94. 中序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
void traversal(TreeNode* root, vector<int>& res)
{
if (root == NULL) return;

traversal(root->left, res); // 左
res.push_back(root->val); // 中
traversal(root->right, res); // 右
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;

traversal(root, res);
return res;
}
};

迭代遍历

144. 前序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 顺序为中左右,因为栈的先入后出的特性,所以代码顺序调整为中右左
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st; // 用栈实现迭代,模拟递归
vector<int> res; // 结果数组

st.push(root);

while (!st.empty())
{
TreeNode* node = st.top();
st.pop();
if (node != NULL)
res.push_back(node->val);
else continue;

st.push(node->right); // 右
st.push(node->left); // 左
}
return res;
}
};

145. 后序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 后序遍历:左右中。前序遍历:中左右 
// 中左右->中右左->左右中
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;

st.push(root);

while (!st.empty())
{
TreeNode* node = st.top();
st.pop();
if (node != NULL) res.push_back(node->val);
else continue;

st.push(node->left); // 左
st.push(node->right); // 右
}
reverse(res.begin(), res.end());
return res;
}
};

94. 中序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 中序遍历的迭代写法,参见总结部分的精髓即可写出以下的代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
TreeNode* cur = root;

// 终止条件:指针和栈都为空
while (cur != NULL || !st.empty())
{
// 指针不为空,则将指针指向的节点放入栈中,指针向左走
if (cur != NULL)
{
st.push(cur);
cur = cur->left;
}
// 指针为空,则将栈顶元素弹出并放入结果数组中,指针向右走
else
{
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};

统一迭代

94. 中序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;

// 将非空的头节点插入栈中
if (root != NULL) st.push(root);

// 循环终止条件:栈为空
while (!st.empty())
{
// 弹出栈顶元素
TreeNode* node = st.top();
st.pop();

// 若node不为空,则按照右中左的顺序访问节点
if (node != NULL)
{
if (node->right) st.push(node->right); // 访问右节点
st.push(node); // 访问中节点
st.push(NULL); // 只访问没处理,在中结点上面添加NULL来标记
if (node->left) st.push(node->left); // 访问左节点
}
// 若node为空,则处理该节点下面的节点,将其加入到res中
else
{
node = st.top();
st.pop();
res.push_back(node->val);
}
}
return res;
}
};

144. 前序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;

if (root != NULL) st.push(root);

while (!st.empty())
{
TreeNode* node = st.top();
st.pop();

// node不为空,访问节点
if (node != NULL)
{
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
st.push(node); // 中
st.push(NULL); // 中节点后面插入NULL
}
// node为空,处理节点
else
{
node = st.top();
st.pop();
res.push_back(node->val);
}
}
return res;
}
};

145. 后序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 统一迭代写法
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;

if (root != NULL) st.push(root);

while (!st.empty())
{
TreeNode* node = st.top();
st.pop();

// 节点不为空,则访问节点,顺序为中右左
if (node != NULL)
{
st.push(node);
st.push(NULL);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
// 节点为空,则处理节点
else
{
node = st.top();
st.pop();
res.push_back(node->val);
}
}
return res;
}
};

心得与备忘录

递归遍历

  1. 记住递归三部曲:
    • 确定递归函数的参数和返回值
    • 确定终止条件
    • 确定单层递归的逻辑
  2. 前序、中序、后序遍历的代码只有单层递归的逻辑部分有所不同。更确切地说,只是三行代码的顺序发生了改变。
  3. 递归的核心函数返回值为void,结果数组以引用的方式作为参数传入,经过核心函数的改变后,改变后的数组会被传出,在主函数中调用其即可。
  4. 易错点:核心函数中忘记加上引用&,插入数组时没有取root指针的值(root->val),而是直接将root指针传入了。
  5. 注意如何写出完整的带有测试样例的代码,这涉及到如何写struct TreeNodemain函数。
  6. 熟悉几个英文单词:
    • 遍历:traversal
    • 前序:pre-order、中序:in-order、后序:post-order、层序:level-order
    • 二叉树:binary tree
    • 递归:Recursion 迭代:Iteration

迭代遍历

  1. 迭代遍历的本质是用栈来模拟递归,用结果数组来收集结果。由于栈的先入后出的特性,前序遍历的顺序本来应该是中左右,迭代写法的顺序调整为中右左。后序遍历是在前序遍历的基础上颠倒右和左的顺序,再翻转结果数组(前序遍历=中左右->中右左->左右中=后序遍历)。
  2. 中序遍历的迭代写法不能像后序遍历那样从前序遍历迭代写法的基础上直接进行改造。这是因为在中序遍历中,遍历节点的顺序与和处理节点的顺序不同。
  3. 中序遍历的迭代写法需要一个指针来遍历所有节点,一个栈用于记录遍历过的节点,一个数组用于存放结果。
  4. 中序遍历迭代写法的精髓:当指针不为空时,用栈记录指针遍历过的元素,指针持续向左走。当指针为空时,从栈中弹出顶部的节点并将其放入结果数组中,然后指针向右走。当指针为空且栈为空时,终止。
  5. 统一迭代的写法可以将前中后序遍历的迭代写法统一起来。
  6. 迭代写法确实更复杂些,注意事项也更多,也更容易写错。了解思路即可,可以放过。

统一迭代

  1. 统一迭代的思路其实比较清晰:当头节点非空时,头节点入栈。在栈非空时,不断循环。弹出栈顶节点,若该节点不为空,则按照顺序访问节点,并在访问中节点之后插入NULL,作为标记(说明该节点只被访问过,没有被处理过);若该节点为空,则处理当前的栈顶节点(原本的栈顶节点已被弹出),将其放入结果数组中,并将其弹出。
  2. 对于前序、中序和后序遍历,只需要改变node不为空时访问节点的顺序即可。考虑到栈先入后出的特性:前序遍历原本的顺序是中左右,调整为右左中。中序遍历原本的顺序是左中右,调整为右中左。后续遍历原本的顺序是左右中,调整为中右左。
  3. 统一迭代思路清晰且对于前中后序遍历能够保持一致的写法,建议用迭代法遍历二叉树时,优先采用统一迭代的写法。前面的迭代遍历的一般写法虽然较为简单,但只能在前序和后序遍历时保持统一,在中序遍历时需要重新写。

链接

239. 滑动窗口最大值
347.前 K 个高频元素
栈与队列总结

知识

239. 滑动窗口最大值

347.前 K 个高频元素

栈与队列总结

初次尝试

239. 滑动窗口最大值

本题应该有些类似于滑动窗口的经典题目:209.长度最小的子数组。本题的思路:用一个长度始终为3的队列,滑过数组。每次算出队列中的最大值,然后存入数组中。我打算另写一个函数来返回三个值中的最大值。但是应该是有办法在队列进出元素的时候顺便维护其中的最大值。

我根据暴力做法的思路,写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
// 得出队列中的最大值
int queuemax(queue<int> q)
{
int max = q.front();
while (q.size())
{
q.pop();
int tmp = q.front();
if (max < tmp) max = tmp;
}
return max;
}

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
queue<int> q;
vector<int> res;

for (int i = 0; i < nums.size(); i ++ )
{
if (q.size() < k) q.push(nums[i]);
else if (q.size() == k)
{
res.push_back(queuemax(q));
q.push(nums[i]);
q.pop();
}
}
res.push_back(queuemax(q));
return res;
}
};

上述代码在输入数组不大时可以正常运行,但输入数组太大时会超时,测试样例通过了37 / 51。上述暴力做法的时间复杂度是O(n * k)。看代码随想录的视频讲解吧。

347.前 K 个高频元素

拿到这道题,我的第一想法是拿哈希去做。但发现哈希不能解决本题,因为对统计频率的数组排序后,数组的下标(即输入数组的元素)被打乱了。直接看卡尔的讲解。

实现

239. 滑动窗口最大值

本题是第一道hard。难点:如何求窗口中的最大值?暴力做法时间复杂度O(n k)。需要一个特殊的队列,实现pop, push和getMaxValue(返回当前队列中的最大值)这三个操作。还可以用一个优先级队列。cpp中的优先级队列就是大顶堆(单调递减)或者小顶堆(单调递增)。大顶堆本质就是一个排序后的二叉树,最大的元素在上面。始终维护大顶堆,让大顶堆不断插入元素和弹出元素,大顶堆最前面的元素就是滑动窗口的最大值。*但是用大顶堆是不行的,因为无法正确地弹出元素(大顶堆内部自动做了排序,打乱了原来元素的顺序)。

因此用优先队列是不行的,需要我们自行实现一个单调队列来解决问题。需要维持队列中的元素是单调递增或单调递减的,同时需要保证pop操作的正确。单调队列中只需要维护有可能成为最大值的元素,而不需要维护k个元素

模拟单调队列:
假设输入数组为13-1-35321。首先在队列中加入元素1,再加入3,若队列的前面有小于3的元素,则将这些元素全部弹出。这样做可以让队列的出口处就是最大值。由于随着滑动窗口的移动,本身就会舍弃第1个1,因此没必要维护3之前比3小的元素。接着在队列中加入-1。此时队列的前面没有小于-1的元素,故-1可以保留在队列中。此时取队首元素3,就是最大值。接着加入-3,队列前面的元素都大于-3,故保留-3,此时队列的最大值还是3。接着加入5,由于5比队列前面的元素都大,因此需要pop掉除5以外的全部元素,此时取队列的最大值,即队首元素,是5。接着放入3,3<5,放入3,此时队列的最大值还是5。接着加入2,2<5&&2<3,因此放入2,此时队列的最大值还是5。再向后移动,需要把最大值5pop掉,加入1,1<2 && 1<3,因此队列中加入1,此时队列的最大值是队首元素3。

单调队列在数组中移动的规则:除去常规的移动窗口的pop和push操作外,若push进来的元素比队列前面的元素都大,那前面的元素都要pop出去,直到队列前面的元素都大于push进来的元素为止。本方法的好处在于getMaxValue时取队首元素即可。

根据原理,我画出了如下的示意图,可以帮助理解(下图中打x的元素是因为单调队列的特殊规则:若push进来的元素比队列前面的元素都大,那前面的元素都要pop出去而被提前被删去的元素)。
Snipaste_2024-02-07_13-50-29.png

根据上述原理,我尝试写出相应的代码,但是有一个问题我始终无法解决:根据规则:若push进来的元素比队列前面的元素都大,那前面的元素都要pop出去,有时原本的队首元素已经被更新为最大的元素了,意味着滑动窗口本身最前面的元素已经被弹出了,但有时,滑动窗口本身最前面的元素还没有被弹出,它仍作为队首元素,需要手动弹出。如何判断是否需要手动弹出队首元素。我来看看卡尔的代码实现,看他是如何解决这个问题的。

卡尔写了单调队列的三个关键函数。单调队列是在双向队列的基础上实现的,双向队列的首尾都可以出入元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
deque<int> que; // cpp中队列默认用deque双向队列来实现,双向队列的首尾都可以出元素和入元素

void pop(int val)
{
// 只有当需要pop的元素和队首元素(单调队列中目前的最大值)相同时,才弹出队首元素
// 例如上图的倒数第二行到最后一行的操作(532->321)
// 若需要pop的元素小于队首元素,那么在push时该元素已经被删除了
// 例如上图中的-1-35->-353,本来需要手动删除-1,但由于-1<5,因此在push(5)时-1已经被删除了
if (!que.empty() && val == que.front())
que.pop_front();
}

void push(int val)
{
// 当队列不为空且要插入的值val > 队列中的最后一个元素时,持续从队尾弹出元素
// 例如上图中的3-1-3->-1-35,要插入5,持续从队尾弹出比5小的元素,然后再插入5
while (!que.empty() && val > que.back()) que.pop_back();
que.push_back(val);
}

int getMaxValue(deque<int> que)
{
return que.front();
}

在上述关键代码的基础上,我写下了解决本题的完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
private:
class MyQueue
{
public:
deque<int> que;
// 单调队列中只维护当前队列中的最大值,作为队首元素
// 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
// 其他值都会在push时被删除
void pop(int val)
{
if (!que.empty() && val == que.front()) que.pop_front();
}

// 保证单调队列从队首到队尾是单调递减的
// 新插入的元素若大于当前队列中的最大值,则删除当前队列,将插入的元素放在队列的首部
void push(int val)
{
while (!que.empty() && val > que.back()) que.pop_back();
que.push_back(val);
}

// 当前队列中的最大值为队首元素,故返回队首元素即可
int getMaxValue()
{
return que.front();
}
};

public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> res;

for (int i = 0; i < k; i ++ )
que.push(nums[i]);

res.push_back(que.getMaxValue());

for (int i = k; i < nums.size(); i ++ )
{
que.pop(nums[i - k]);
que.push(nums[i]);
res.push_back(que.getMaxValue());
}
return res;
}
};

347.前 K 个高频元素

两个难点:

  • 如何求数组中每个元素的频率

  • 如何对这个频率进行排序,并求前k个高频的元素

用map来进行排序,key用来存放元素,value用来存放元素出现的次数。接着以value为基准做从大到小的排序(不好做,因为map默认是按照key的顺序来进行排序的),最后输出value对应的key即可。时间复杂度O(nlogn)

求前k个高频的元素,只需维护k个有序的集合,没必要对所有元素都进行排序。经典的数据结构:大顶堆、小顶堆。堆擅长在很大的数据集中求前k个高/低频的元素。大顶堆的根节点是最大的元素,小顶堆的根节点是最小的元素。

如何用堆解决这个问题?用堆去遍历map中的所有元素(以value为基准进行统计),堆中维持k个元素,遍历完map中的所有元素后,堆中的k个元素就是前k个高频元素。大/小顶堆?用大顶堆遍历map中的所有元素时,遇到新元素时,将其插入到大顶堆中,会弹出堆顶的元素(最大的元素),用大顶堆遍历完map后,堆中剩下的元素是前k个低频的元素因此要用小顶堆。小顶堆每次在push进来元素时,弹出堆顶元素(最小的元素),堆中剩下的就是最大的元素。最后输出前k个最大的value对应的key。时间复杂度:遍历数组O(n),每次堆中元素调整O(logk)(堆中有k个元素,堆是树状结构),总时间复杂度为O(nlogk)。在数组很大,k较小的情况下,本做法的性能明显优于对整个map进行排序的性能。优先级队列的底层实现是堆,因此用优先级队列即可。可自行实现大顶堆和小顶堆。

参考代码随想录的代码,我写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
class compare
{
public:
// 为定义小顶堆重载运算符,这里的函数名为operator(),而非operator
// 对大顶堆,本来应该是右边的元素>左边的元素,对小顶堆,则与此相反
bool operator() (pair<int, int> lhs, pair<int, int> rhs)
{
return lhs.second > rhs.second; // 比较的是元素出现的次数,而非元素的值
}
};

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;

// nums[i]作为key, 出现此处作为value存入map中
for (int i = 0; i < nums.size(); i ++ )
map[nums[i]] ++ ;

// 定义小顶堆,其中的元素类型是pair<int, int>,底层实现是vector<pair<int, int>>
priority_queue<pair<int,int>, vector<pair<int, int>>, compare> q;

// 遍历map,不断将map中的元素插入小顶堆中,小顶堆不断弹出根节点处最小的元素
// 最后剩下的k个元素是出现频次最高的k个元素
for (auto it = map.begin(); it != map.end(); it ++ )
{
q.push(*it);
if (q.size() > k) q.pop();
}

vector<int> res(k);

// 根节点处是最小的元素,越往下元素越大,因此将小顶堆中的k个元素倒着插入res中
for (int i = k - 1; i >= 0; i -- )
{
res[i] = q.top().first; // 插入res的是key, 即nums[i]
q.pop();
}
return res;
}
};

心得与备忘录

239. 滑动窗口最大值

  1. 单调队列需要手动实现,cpp标准库中没有现成可用的单调队列。
  2. 单调队列的好处在于能够将当前队列中的最大值放在队首,且不改变其他值的排列顺序(即其他值在单调队列中的排列顺序和它们在输入数组中的排列顺序相同)。
  3. 单调队列的特殊规则:若push进来的元素比队列前面的元素都大,那前面的元素都要pop出去。
  4. 定义一个类,在双向队列的基础上实现单调队列,而不要试图在主函数中对queue<int>做加工。
  5. 本题的详细模拟流程见实现中的图片。
  6. 单调队列中定义了三个函数:pop, push和getMaxValue。
    对pop函数(负责模拟窗口的滑动,删除队首的最大值),需要注意:

    • 单调队列中只维护当前队列中的最大值,作为队首元素
    • 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
    • 其他值都会在push时被删除

    对push函数(负责向单调队列中插入元素,同时调整队列中元素的顺序,将最大值置于队首),需要注意:

    • 保证单调队列从队首到队尾是单调递减的
    • 新插入的元素若大于当前队列中的最大值,则删除当前队列,将插入的元素放在队列的首部
    • 当前队列中的非最大值会在不断调用push函数的过程中被删除,最大值则需要pop函数来删除
  7. 时间复杂度: O(n) 空间复杂度: O(k)
    输入数组中的每个元素在单调队列中最多也就被插入和弹出各一次,没有任何多余操作,所以整体的时间复杂度还是O(n)。空间复杂度因为我们定义一个辅助队列,所以是O(k)。
  8. 本题之所以选择在双向队列的基础上加工出单调队列,是因为双向队列可以方便地在队首和队尾插入和删除元素。
  9. 注意类的写法、双向队列的push_back, push_front, pop_back, pop_front以及单调队列的push, pop等方法,不要写错或者混淆。

    347.前 K 个高频元素

  10. 本题的大致思路:用map来存储元素的值和出现次数,用一个小顶堆遍历map,最终获取出现次数最高的k个元素。
    map->priority_queue->vector

  11. 本题的思路:用map的key存储元素的值,value存储元素出现的次数。定义一个小顶堆。遍历map,不断将map中的元素插入到小顶堆中,不断弹出小顶堆根节点处的元素,最后小顶堆中剩下的k个元素就是出现次数最高的k个元素。将这k个元素倒着插入结果数组中即可。
  12. 为什么使用小根堆:小跟堆根节点处的元素最小,每次弹出元素也是从根节点处弹出,因此用大小为k的小根堆遍历完map后,小根堆中的k个元素是出现次数最高的k个元素,较小的元素在遍历的过程中就已经被弹出了。
  13. 注意小顶堆的定义方式:在优先级队列的基础上,传入的参数分别为小顶堆中存储的元素类型,小顶堆的底层实现,自定义的compare类(用于实现小顶堆根节点是最小元素的特性)。
  14. 注意如何写compare类,关键在于重载运算符。
  15. 注意vector数组是可以定义大小的,定义方式为vector<int> res(k),vector元素定义了大小之后,就能像普通数组那样用索引给元素赋值:res[i],插入元素的push_back函数并不是必须的。
  16. 根据小根堆的特点,res数组需要倒着插入,即从下标k - 1处开始插入。
  17. 定义类是,要记得在类中的函数前加上public,否则无法正常调用类中的函数。
  18. 本算法的时间复杂度是O(nlogk),好于对map全部排序的O(nlogn),在n较大,k较小时性能提升尤为明显。

栈与队列总结

  1. 栈和队列的理论基础:栈先入后出,队列先入先出
  2. 用两个栈实现队列,用一个队列实现栈
  3. 栈的应用:栈的应用相对较为简单且单一。栈特别适合处理对相邻字符需要做特殊判断的一些问题。比如相邻的括号匹配(20. 有效的括号)、相邻字符的消除(删除字符串中的所有相邻重复项)和后缀表达式中相邻数字的计算(逆波兰表达式求值)。
  4. 队列的应用:队列的应用更为复杂且多样,包括手动实现单调队列(239. 滑动窗口最大值)和手动实现大/小顶堆(优先级队列)347. 前k个高频元素)。对于队列的应用要多复习,这两题写起来都较为复杂。
  5. 单调队列不是一成不变的,而是不同场景不同写法。不要以为239. 滑动窗口最大值中的单调队列实现就是固定的写法。
  6. 栈里面的元素在内存中是连续分布的么?

    这个问题有两个陷阱:

    • 陷阱1:栈是容器适配器,底层容器使用不同的容器,导致栈内数据在内存中不一定是连续分布的。
    • 陷阱2:缺省情况下,默认底层容器是deque,那么deque在内存中的数据分布是什么样的呢? 答案是:不连续的,下文也会提到deque。
  7. 拓展题:71. 简化路径
  8. 优先级队列就是大/小顶堆,名字虽为队列(因为优先级队列对外接口只是从队头取元素,从队尾添加元素,再无其他取元素的方式,看起来就是一个队列),但本质是完全二叉树。大顶堆(堆头是最大元素),小顶堆(堆头是最小元素)。从小到大排就是小顶堆,从大到小排就是大顶堆。大小顶堆和大小根堆是相同的。

链接

20. 有效的括号
1047. 删除字符串中的所有相邻重复项
150. 逆波兰表达式求值

知识

20. 有效的括号

  1. cpp中,将一个个字母存储在stack中,用stack<int>或者stack<char>都是一样的。若是stack<int>,则字符以ascii码的形式存储。
  2. 在Linux系统中,cd(change directory)命令用于更改当前工作目录。它确实可以借助栈的概念来理解路径的导航,尤其是处理相对路径时。

    考虑命令cd a/b/c/../../,这里我们可以将目录路径视作一个栈的操作序列:

    cd a:进入目录a,相当于将a压入栈。
    cd b:进入子目录b,相当于将b压入栈中a的上面。
    cd c:进入子目录c,相当于将c压入栈中b的上面。
    此时栈的状态为:

    1
    2
    3
    c
    b
    a

    然后遇到..,这代表上一级目录,相当于从栈中弹出最上面的元素。第一个..将c弹出。
    栈的状态更新为:

    1
    2
    b
    a

    第二个..将b弹出。
    最终栈的状态为:

    1
    a

    所以,最后当前工作目录是a。在这个过程中,我们可以将每个目录视为栈中的一个元素,每进入一个新的子目录就相当于压入一个元素,而每次使用..就相当于弹出一个元素,回到上一级目录。这就是栈数据结构在文件系统路径解析中的一个应用。

初次尝试

20. 有效的括号

不知道怎么做,直接看卡尔的讲解视频。

1047. 删除字符串中的所有相邻重复项

本题应该是一道用栈解决的经典问题。以输入s = “abbaca”为例,定义一个栈,遍历字符串,遍历到第一个字符时,判断栈顶元素是否与之相同,是,则弹出栈顶元素,否,则插入该字符。对后面的字符也是这样处理的。根据这个思路,我独立写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;

for (int i = 0; i < s.size(); i ++ )
{
if (st.empty()) st.push(s[i]);
else if (s[i] == st.top()) st.pop();
else st.push(s[i]);
}
string out;
while (st.size())
{
out += st.top();
st.pop();
}
reverse(out.begin(), out.end());
return out;
}
};

需要特别注意:

  • 对栈做top操作时需要保证其非空,否则会报访问未知地址,导致程序非法访问内存的错误
  • 将栈中的一个个元素弹出并插入到一个字符串中后,需要将字符串颠倒顺序,输出才是正确的顺序

150. 逆波兰表达式求值

我看题后,暂时还没有解题思路。先看视频,了解本题的解题思路。

实现

20. 有效的括号

本题是用栈来解决的经典题目。栈的应用:编译器做词法分析、linux系统的命令。

不匹配的场景共有三个:

  1. 多出左括号
  2. 括号的类型不匹配
  3. 多出右括号

各种不匹配的场景都可被归为以上三类。

如何用栈结构解决三类不匹配的情形?

对1,从字符串的左边向右边遍历,遇到左括号,就将一个对应的右括号加入到栈中。当遍历到字符串的右括号时,若栈顶元素和右括号相同,则弹出栈顶元素。如果字符串遍历完了,但栈不为空,栈中还剩余右括号,就说明字符串中的左括号多了,不匹配。

对2,从左往右遍历字符串,遇到左括号,就在栈中加入一个对应的右括号。遇到右括号,将其与栈顶的元素比较,若不相同,则说明不匹配。

对3,从左往右遍历字符串,遇到左括号,就在栈中加入一个对应的右括号。遇到右括号,将其与栈顶的元素比较,相同则弹出栈顶的元素。若字符串还没遍历完,栈就空了,说明字符串的前面没有左括号与后面的右括号对应,说明多出了右括号,也不匹配。

字符串遍历完之后,栈是空的,就说明全都匹配了。

剪枝:字符串长度为奇数,一定会有不匹配的括号,直接return false即可。

看了卡尔的视频后,我写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool isValid(string s) {
stack<int> st; // stack<int>和stack<char>都可以

// 剪枝:字符串长度为奇数,一定不匹配
if (s.size() % 2) return false;

for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == '(') st.push(')');
else if (s[i] == '[') st.push(']');
else if (s[i] == '{') st.push('}');
// 不匹配的两种情况:多出右括号和括号类型不匹配
// 两个判据不可颠倒,否则可能会出现栈为空但依然试图取栈顶元素的情况,编译器会报错
else if (st.empty() || s[i] != st.top()) return false;
// 栈不为空且栈的顶元素和s[i]相同,则弹出st的顶元素,两两抵消
else st.pop();
}
// 不匹配的情况:多出左括号
return st.empty();
}
};

1047. 删除字符串中的所有相邻重复项

本题用栈解决非常简单,用其他数据结构比较复杂。本题和20. 有效的括号是同一类问题。本题的主要思路:相邻的字母相同,就做消除的动作。

栈用来存遍历过的元素,同时帮助我们完成消除的动作。本题可以用一个字符串来模拟栈的行为,这样在输出时就不需要再把栈转换为字符串了。用字符串模拟栈时,可以让字符串的尾部作为栈顶,字符串的头部作为栈底,这样字符串中字符的顺序就是正确的。

根据以上原理,我写出了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
string removeDuplicates(string s) {
string out;

for (int i = 0; i < s.size(); i ++ )
{
if (out.empty()) out.push_back(s[i]);
else if (s[i] == out.back()) out.pop_back();
else out.push_back(s[i]);
}
return out;
}
};

可以将上述代码写的更为精简(将两种需要push_back()的情况合并为一种):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string removeDuplicates(string s) {
string res;

for (int i = 0; i < s.size(); i ++ )
{
// 字符串为空或者字符串尾部的元素与s[i]不同时,直接在字符串的尾部插入s[i]
if (res.empty() || res.back() != s[i]) res.push_back(s[i]);
// 否则,意味着字符串尾部的元素和s[i]相同,则两两抵消,弹出字符串尾部的元素
else res.pop_back();
}
return res;
}
};

相比于我在初次尝试中空间复杂度为O(n)的做法,上面的做法空间复杂度是O(1),因为返回值不计空间复杂度。

150. 逆波兰表达式求值

什么是逆波兰表达式:是后缀表达式。后缀表达式是方便计算机来做运算的一种表达式。我们正常易于阅读的表达式是中缀表达式。例如(1+2)x(3+4)。画成二叉树的形式:

1
2
3
4
5
6
7
8
graph TD;
A[x] --> B[+];
A --> C[+];
B --> D[1];
B --> E[2];
C --> F[3];
C --> G[4];

后缀表达式就是上述二叉树的后序遍历后续遍历的顺序是左右中。因此后缀表达式是:12+34+x。二叉树的中序表达式是1+2x3+4。中序表达式若要得到正确的结果,需要加上括号。但后缀表达式我们不需要加任何括号,从头到尾遍历我们就可以计算出正确的结果。计算机只需顺序处理后缀表达式,即可得到计算结果,而不必担心括号优先级,这就是为什么说后缀表达式是方便计算机来做运算的一种表达式

计算机如何顺序处理后缀表达式?用栈。遍历后缀表达式时,遇到数字就将数字加入栈中,遇到运算符就从栈中取出元素来做运算,再把运算结果加入栈中。以上面的后缀表达式为例,先将1和2加入栈中,遇到+,则弹出2和1,算2+1=3,将3加入栈中。再将3和4加入栈中,遇到+,则弹出4和3,算4+3=7,将7加入栈中。遇到x,栈中弹出7和3,算7x3=21。最后将21加入栈中。后缀表达式的结果就是栈中最后的元素。

总结:两个数字遇到一个操作符时,也做消除操作,将合成的数字加入到栈中。栈适合做相邻字符的消除操作。

根据以上原理,我参照代码随想录的代码写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int evalRPN(vector<string>& s) {
stack<long long> st;

for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/")
{
// 注意采用long long类型
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
// 注意是先num2再num1
if (s[i] == "+") st.push(num2 + num1);
else if (s[i] == "-") st.push(num2 - num1);
else if (s[i] == "*") st.push(num2 * num1);
else st.push(num2 / num1);
}
else
st.push(stoll(s[i])); // stoi可以将字符串转换为int, stoll可以将字符串转换为long long
}
int res = st.top();
st.pop(); // 释放内存
return res;
}
};

本题关于数字的变量类型全部用int而不用long long,也可以通过评测。

心得与备忘录

20. 有效的括号

  1. 本题的思路:在字符串中遇到左括号就在栈中插入右括号,在字符串中遇到右括号则判断其能否与栈顶元素相消。
  2. 不匹配的三种情况:多出右括号、多出左括号、括号类型不匹配。
  3. 本题利用了栈的性质:后插入的元素先弹出,这与本题字符串中后出现的左括号必然有先出现的右括号与之匹配的题意相符。
  4. st.empty()s[i] != st.top()这两个判据顺序不可颠倒,否则会出现栈为空但依然试图取栈顶元素的情况,编译器会报错。
  5. 本题可以做剪枝优化:字符串长度为奇数,则必然不匹配。
  6. 栈用stack<int>或者stack<char>都可以。前者就是将字符存储为ascii码。

1047. 删除字符串中的所有相邻重复项

  1. 栈特别适合处理对相邻字符需要做特殊判断的一些问题。比如相邻的括号匹配和消除。
  2. 字符串类型的变量也有empty, back, pop_back, push_back等函数。
  3. 本题可以用字符串来模拟栈,这样返回时不需要将栈转换回字符串,且可以通过让字符串头部对应栈底,字符串尾部对应栈顶的方式,来让输出的字符串不需要调整顺序(即不需要reverse)
  4. 本题需要考虑三种情况:栈为空/栈顶元素和字符串中元素相同/不相同
  5. 函数的递归调用需要用到栈
  6. 一个函数的返回值不会被计入这个函数的空间复杂度,额外的空间占用才会被计入空间复杂度

150. 逆波兰表达式求值

  1. 栈适合用于做相邻两个字符的消除操作。
  2. 逆波兰表达式即为二叉树的后缀表达式。
  3. 后缀表达式由二叉树的后序遍历(按左右中的顺序)得到。
  4. 本题思路:遇到数字则将其插入栈中,遇到运算符就弹出栈中的两个数字,计算并将计算结果插入栈中。
  5. 注意:运算时先num2(后弹出的数字,二叉树的左子节点)后num1(先弹出的数字,二叉树的右子节点)。
  6. stoi可以将字符串转换为int,stoll可以将字符串转换为long long。
  7. 本题无需采用long long类型变量,用int类型变量就可以通过测评。

链接

栈与队列理论基础
232.用栈实现队列
225. 用队列实现栈

知识

栈与队列理论基础

顾名思义,队列是先进先出,栈是先进后出(可以从顶部添加元素,也可以从顶部移除元素,但是不能从中间或底部添加或移除元素)。

栈与队列理论1

栈和队列是STL(C++标准库)里面的两个数据结构。STL有多个版本,其中有三个版本最为普遍。我们介绍的栈和队列是三个版本中的SGI STL里面的数据结构。知道版本才确定其底层实现。

栈:先进后出
栈与队列理论2

栈提供push和pop等等接口,时间复杂度都是O(1),所有元素必须符合先进后出规则(只能在顶部添加和移除元素),所以栈不提供走访功能,也不提供迭代器(iterator)。 不像是set 或者map提供迭代器iterator来遍历所有元素。

我们可以用多种容器来实现栈的功能,栈的底层实现可以是vector,deque(双端队列),list(双向链表)都是可以的, 主要就是数组和链表的底层实现。

我们常用的SGI STL,如果没有指定底层实现的话,默认是以deque为缺省情况下栈的底层结构(deque是容器)。deque是一个双向队列,只要封住一段,只开通另一端就可以实现栈的逻辑了SGI STL中 队列底层实现缺省情况下一样使用deque实现的。也可以指定vector为栈的底层实现,初始化语句如下:

1
2
3
// 第一个参数int:指定了栈中元素的类型
// 第二个参数std::vector<int>:指定了底层容器的类型及其元素类型。即使用一个整型向量来存储栈中的元素。
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈

通过允许指定底层容器,std::stack提供了灵活性,可以根据不同的性能需求或使用场景来选择最合适的容器类型。例如,std::vector提供了随机访问的能力,但是在容器前端添加或删除元素可能较慢,而std::deque在容器的前端和后端添加或删除元素都较快,但不支持快速随机访问。选择哪种底层容器取决于你的具体需求。

队列是先进先出的数据结构,同样不允许有遍历行为,不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

也可以指定list 为起底层实现,初始化queue的语句如下:

1
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

STL队列和栈都不被归类为容器,而被归类为container adapter(容器适配器)。因为可以用不同的容器来实现栈和队列的功能,因此栈和队列不对应于某个特定的容器

初次尝试

232.用栈实现队列

yxc讲过的应该是用数组来实现栈和队列,并没有见过怎么用栈来实现队列。直接看卡尔的讲解。

225. 用队列实现栈

我想了想,没想出什么好办法,听卡尔讲吧。

实现

232.用栈实现队列

不涉及具体的算法,考察对栈和队列的基本操作。向队列中插入元素123,则队列吐出元素的顺序是123。向栈中插入元素123,则栈吐出元素的顺序是321。若想用栈实现队列,就需要两个栈,一个栈用于存储元素,另一个栈用于改变第一个栈中元素出栈的顺序。第一个栈吐出元素的顺序是321,将它们依次插入第二个栈中,则第二个栈吐出元素的顺序是123。第一个栈被称为入栈,第二个栈被称为出栈。

tstmp_20240205061240

入栈中不要有滞留元素的行为,一旦需要弹出元素,就把入栈中的所有元素全部放入出栈中,让出栈实现元素的弹出。如果没有把入栈中的所有元素全部放入出栈,则出栈中弹出元素的顺序会与队列弹出元素的顺序不同。

本题pop函数的实现需要特别注意。若出栈为空,则将入栈中的所有元素加入到出栈中。peek和pop方法大部分代码都是重复的,可以在peek中直接调用pop方法:result = this->pop();。此时第一个元素被获取的同时也被弹出了,因此需要将其插入回去:stackOut.push(result)(peek方法只需要查询元素的数值,不需要像pop函数那样弹出元素)。参考视频讲解中的伪代码,我写出了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MyQueue {
public:

stack<int> inStack; // 入栈
stack<int> outStack; // 出栈

MyQueue() {
}

void push(int x) {
// 向入栈中插入元素即可
inStack.push(x);
}

int pop() {
// 若出栈为空,则将入栈中的所有元素全部加入到出栈中
// 如果没有把入栈中的所有元素加入到出栈中,则弹出元素的顺序会发生错误
// 若出栈不为空,则跳过if判断部分,直接执行本函数最后三行代码
if (outStack.empty())
{
while (inStack.size())
{
int tmp = inStack.top();
inStack.pop();
outStack.push(tmp);
}
}

// 返回出栈顶部的元素并将该元素弹出
int res = outStack.top();
outStack.pop();
return res;
}

int peek() {
// 复用上面实现的pop函数
int res = this->pop();
// 由于pop函数弹出了出栈顶部的元素,peek函数只需要查询出栈顶部的元素,不需要弹出
// 因此将该元素插入回出栈中
outStack.push(res);
return res;
}

bool empty() {
// 入栈和出栈同时为空时,队列才为空
// 若只有入栈为空,则出栈中依然有元素没有弹出,说明队列还可以弹出元素,不为空
// 若只有出栈为空,则入栈中依然有元素可以加入出栈中,之后出栈还可以继续弹出元素,故队列也不为空
if (inStack.empty() && outStack.empty()) return true;
else return false;
}
};

225. 用队列实现栈

两个栈才能实现一个队列。虽然两个队列可以模拟栈,但重点讲一个队列模拟栈的进元素和出元素

用两个队列模拟栈:假设栈中先后插入元素123,则栈弹出元素的顺序为321。那么我们可以在队列1中先插入123,然后将1和2放入队列2中,然后从队列1中弹出元素3。接着若想让队列1弹出元素2,则将队列2中的元素2放入队列1中即可。详细讲解见代码随想录网站。

用一个队列模拟栈:在队列中先加入123,然后取出元素1,加入队列中;再取出元素2,加入队列中,此时队列弹出的元素就是3。推广:队列中有size个元素,先弹出(size - 1)个元素,再将它们加入队列中,再弹出队列中剩余的最后一个元素即可

根据上述原理,我独立写出了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MyStack {
public:
queue<int> q;

MyStack() {
}

void push(int x) {
q.push(x);
}

int pop() {
int count = q.size(); // 队列中有size个元素
// 循环(size - 1)次
// 先弹出队首的元素,再将其加入到队尾中
while (count > 1)
{
int tmp = q.front();
q.pop();
q.push(tmp);
count -- ;
}
// 弹出队首的元素,即为最后插入的元素
int res = q.front();
q.pop();
return res;
}

// 复用pop函数,但是由于本函数只需要实现查询元素的功能,要记得将弹出的元素插入回去
// 也可直接return q.back()。因为栈顶的元素就是队列尾部的元素(队列中,从front弹出元素,从back插入元素)
int top() {
int res = this->pop();
q.push(res);
return res;
}

// 队列为空,则栈也为空
bool empty() {
return q.empty();
}
};

更简洁的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MyStack {
public:
queue<int> q;

MyStack() {

}

void push(int x) {
q.push(x);
}

int pop() {
int size = q.size();
size -- ;
while (size -- )
{
q.push(q.front());
q.pop();
}
int res = q.front();
q.pop();
return res;
}

int top() {
return q.back();
}

bool empty() {
return q.empty();
}
};

用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。据此原理,我写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MyStack {
public:
queue<int> q1;
queue<int> q2;

MyStack() {

}

void push(int x) {
q1.push(x);
}

int pop() {
// 将除去队尾的元素的其他元素全部加入到q2中
int size = q1.size();
size -- ;
while (size -- )
{
q2.push(q1.front());
q1.pop();
}
// 收获答案
int res = q1.front();
// 将q2赋给q1
q1 = q2;
// 清空q2
while (q2.size()) q2.pop();
return res;
}

int top() {
return q1.back();
}

bool empty() {
return q1.empty() && q2.empty();
}
};

心得与备忘录

232.用栈实现队列

  1. 注意stack内置的pop函数不会返回被移除的元素的值。
  2. 实现pop函数时:出栈为空,则插入入栈中的所有元素;出栈不为空,则直接弹出出栈中的首元素。
  3. 一旦需要弹出元素,就把入栈中的所有元素全部放入出栈中,否则出栈中弹出元素的顺序会与队列弹出元素的顺序不同。
  4. 入栈和出栈都为空时,模拟的队列才为空。
  5. 取出栈顶元素再弹出栈顶元素的实现,都是先int tmp = stack.top(),再stack.pop()

225. 用队列实现栈

  1. 本题的关键在于如何弹出元素。
  2. 队列中,从front弹出元素,从back插入元素。取出队列尾部的元素:queue.back(),取出队列头部的元素:queue.front()
  3. 掌握一个队列实现栈的方法即可,两个队列实现栈更加复杂。