YifanChen's Blog

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

0%

发表于 更新于 分类于

链接

235. 二叉搜索树的最近公共祖先
701.二叉搜索树中的插入操作
450.删除二叉搜索树中的节点

初次尝试

235. 二叉搜索树的最近公共祖先

拿到本题，我发现这道题和236. 二叉树的最近公共祖先基本相同，只不过二叉树的条件被增强为二叉搜索树。我首先尝试用236题的思路和代码解决本题。据此，我独立写出了以下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 终止条件1
        if (root == NULL) return NULL;
        // 终止条件2
        if (root == p || root == q) return root;

        // 后序遍历
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root;
        if (left) return left;
        if (right) return right;
        return NULL;
    }
};

然后尝试利用二叉搜索树的特性来进行优化。我想到的优化是：用双指针后序遍历二叉搜索树，若pre和cur分别指向两个目标节点，那么cur就是两节点的最近公共祖先。直接看卡尔的讲解吧。

701.二叉搜索树中的插入操作

本题应该充分利用二叉搜索树的性质就可以求解。若插入节点的值大于当前节点，则向当前节点的右子树插。若插入节点的值小于当前节点，则向当前节点的左子树插。我选择的策略是尽量往叶子节点那一层插入。根据这个思路，我写下了如下的代码（迭代写法，实际上就是枚举将val节点插入二叉搜索树的各种可能）：

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:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // root为空，则直接返回由val创建的节点
        if (root == NULL) return new TreeNode(val);
        
        // 后序移动cur指针，不要直接移动root
        TreeNode* cur = root;

        while (cur)
        {
            // cur无左子节点的情况，则条件合适就将val节点作为cur的左子节点
            if (cur->left == NULL && val < cur->val)
            {
                TreeNode* insert = new TreeNode(val);
                cur->left = insert;
                return root;
            }
            
            // cur无右子节点的情况，则条件合适就将val节点作为cur的右子节点
            if (cur->right == NULL && val > cur->val)
            {
                TreeNode* insert = new TreeNode(val);
                cur->right = insert;
                return root;
            }
            
            // 否则继续走到叶子节点位置，在叶子节点之下插入val节点
            if (val > cur->val) cur = cur->right;
            else if (val < cur->val) cur = cur->left;
            if (cur->left == NULL && cur->right == NULL) 
            {
                TreeNode* insert = new TreeNode(val);
                if (val > cur->val) cur->right = insert;
                else cur->left = insert;
                return root;
            }
        }
        // 必须随便返回一个东西，虽然必然不会执行这行代码，但不返回一个东西本程序就会报错
        return NULL;
    }
};

注意，上述写法一定要区分cur指针和root节点。在写出了迭代写法后，应该也可以根据相同的原理写出递归写法。递归的写法其实非常简单，我尝试了一段时间后写出了如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // 终止条件
        if (root == NULL) return new TreeNode(val);
        
        // 要插入的节点的值小于root节点的值，则将其插入root节点的左子树
        if (root->val > val)  root->left = insertIntoBST(root->left, val);
        // 要插入的节点的值大于root节点的值，则将其插入root节点的右子树
        else if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

450.删除二叉搜索树中的节点

本题的难点在于删除二叉搜索树中的节点后，要调整二叉树的结构，甚至要改变root节点。我想到的办法就是中序遍历时使用双指针。当cur指针找到要删去的节点时，cur指针再向后移动一位，然后直接用cur指针指向pre指针，就完成了对要删去节点的删除。根据这个算法思路，我尝试写代码，但写不出来，直接看卡尔的讲解。

实现

235. 二叉搜索树的最近公共祖先

基于236. 二叉树的最近公共祖先，要好好利用二叉搜索树的特性。思路：从上往下遍历二叉树，若当前遍历的节点的值大于p和q的值，则p和q的最近公共祖先一定在当前节点的左子树中，此时从当前遍历的节点开始向左遍历。若当前遍历的节点的值小于p和q的值，则p和q的最近公共祖先一定在当前节点的右子树中，此时从当前遍历的节点开始向右遍历。若当前遍历的节点的值在p和q之间，则当前节点就是p和q的公共节点。

现在的问题是，当前节点是否是p和q的最近公共祖先？其实是的。因为p和q分别在当前节点的左右子树中，如果从当前节点开始继续向下遍历，那么不是错过p就是错过q。接下来开始写递归法的代码。

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
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
{
    // 终止条件
    if (cur == NULL) return NULL;
    
    // 单层递归逻辑
    // 本题不用涉及前中后序，因为二叉搜索树本身是有序的，只要有左和右即可，中在哪里都可以
    // 若当前遍历的节点的值大于p和q的值，则p和q的最近公共祖先一定在当前节点的左子树中，此时从当前遍历的节点开始向左遍历
    if (cur->val > p->val && cur->val > q->val)
    {
        TreeNode* left = traversal(cur->left, p, q);
    	  // 在向左遍历的过程中找到了p和q的最近公共祖先，则返回之
    		if (left != NULL) return left;
    }
    
    // 若当前遍历的节点的值小于p和q的值，则p和q的最近公共祖先一定在当前节点的右子树中，此时从当前遍历的节点开始向右遍历
    if (cur->val < p->val && cur->val < q->val)
    {
        TreeNode* right = traversal(cur->right, p, q);
        // 在向右遍历的过程中找到了p和q的最近公共祖先，则返回之
        if (right != NULL) return right;
    }
    
    // 剩下的情况：当前节点的值在p和q之间，则当前节点就是p和q的最近公共祖先
    return cur;
}

本题迭代法的代码也比较简单，原因是二叉搜索树确定了搜索的方向。迭代法代码如下所示：

1
2
3
4
5
6
7
8
9
10
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
{
    while (cur)
    {
        if (cur->val > p->val && cur->val > q->val) cur = cur->left;
        else if (cur->val < p->val && cur->val < q->val) cur = cur->right;
        else return cur;
    }
    return NULL; // 一定不要忘记这句话，否则函数会因为没有返回值报错
}

对于二叉搜索树的题目，迭代法似乎比递归法还更简单。

701.二叉搜索树中的插入操作

插入新节点的方式有多种，得到的二叉搜索树不唯一。必然可以在二叉搜索树的叶子节点处插入新的节点。若在二叉搜索树的其他位置处插入节点，则改变了二叉搜索树的结构，将本题做复杂了。递归法代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* insert(TreeNode* root, int val)
{
    // 终止条件
    // 卡尔的理解：遍历到空节点（叶子节点的左子节点或右子节点）时，将val节点作为叶子节点的左子节点或者右子节点
    // 此时将val节点向上返回给叶子节点
    // 卡尔的理解方式比较复杂，不如直接理解为传入一个空的树，返回根据val创建的新节点即可
    if (root == NULL) 
    {
        TreeNode* node = new TreeNode(val);
        return node;
    }
    
    // 卡尔的理解：在val节点作为叶子节点的左子节点时，当前节点的左指针指向val节点
    // 在val节点作为叶子节点的右子节点时，当前节点的右指针指向val节点
    if (val < root->val) root->left = insert(root->left, val);
    if (val > root->val) root->right = insert(root->right, val);
    
    return root;
}

卡尔相当于是从叶子节点开始，自下往上讲解递归法的原理。我的理解方式是从root节点开始，自上而下的理解递归的思路。我的理解方式要简单一些，有利于快速写出本题的递归版本的代码。本题也可以用迭代法，由于是二叉搜索树明确了搜索的方向，所以迭代法的代码也会比较简单。

看了代码随想录的讲解后，我独立写出了正统的迭代法的代码：

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:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // 终止条件
        if (root == NULL) return new TreeNode(val);
        
        // 用cur节点作为当前遍历到的节点，用parent节点作为cur节点的父节点
        // 因为最后是在叶子节点下插入新节点，因此cur节点必定会遍历到空节点，此时需要利用parent节点来指向新节点
        TreeNode* parent = new TreeNode(0);
        TreeNode* cur = root;
        
        // cur == NULL时终止循环
        while (cur)
        {
            // parent节点随着cur节点移动，但始终落后一步，因此parent节点是当前节点的上一个节点（父节点）
            parent = cur; 
            // 根据二叉搜素树的有序性移动cur节点
            if (val < cur->val) cur = cur->left;
            else cur = cur->right;
        }
        
        // 最终在二叉搜索树的叶子节点下插入新节点，这就需要用到parent节点，因为cur节点已经为空
        if (val < parent->val) parent->left = new TreeNode(val);
        else parent->right = new TreeNode(val);
        return root;
    }
};

正统的迭代法采取的是双指针的思路，需要两个节点，一个是cur节点，其是遍历二叉搜索树时的当前节点。另一个是parent节点，其是当前节点的上一个节点（父节点）。

450.删除二叉搜索树中的节点

删除节点后，要保证二叉树依然是二叉搜索树。本题比较难，因为要修改二叉树的结构。删除节点后的二叉树结构不唯一，只要符合二叉搜索树的定义即可。下面开始分析可能的情况。

  • 没找到要删除的节点
  • 要删除的节点是叶子节点，左为空，右也为空（此时删除节点较为简单，因为不需要改变二叉树的结构）
  • 要删除的节点左不为空，右为空。则让该节点的父节点直接指向该节点的左子节点
  • 要删除的节点左为空，右不空。则让该节点的父节点直接指向该节点的右子节点
  • 要删除的节点左不空，右不空。本情况最复杂，因为要大幅调整二叉搜索树的结构。拿以下二叉树为例：
    tstmp_20240424064451

例如删去节点7。让7的右子树继位，那么7的左子树应该放在右子树的哪里。7的左子树应该放在右子树中的左下角（右子树中的最小值）。让7的左子树继位也可以，原理相同。

接下来开始写代码（代码不多但不好理解）：

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
// 不写cpp中需要释放内存的逻辑，只写核心代码
// 返回新二叉树的根节点
TreeNode* delete(TreeNode* root, int key)
{
    // 终止条件
    // 不需要遍历整个二叉树，找到要删除的点就是终止条件
    // 找到要删除的点后就要删除该点，因此删除该点的操作在终止条件中
    
    // 没找到要删除的节点/传入的二叉树为空
    if (root == NULL) return NULL;
    
    // 找到了要删除的节点
    if (root->val == key)
    {
        // 要删除的节点是叶子节点，左为空，右也为空
        // return NULL的意思是该节点的父节点指向NULL
        if (root->left == NULL && root->right == NULL) return NULL;
        
        // 要删除的节点左不为空，右为空
        // 将要删除的节点的左孩子直接向上返回即可
        else if (root->left && root->right == NULL) return root->left;
        
        // 要删除的节点左为空，右不空
        // 将要删除的节点的右孩子直接向上返回即可
        else if (root->left == NULL && root->right) return root->right;
        
        // 要删除的节点左不空，右不空
        else
        {
            TreeNode* cur = root->right; // 要删除节点的右子树
            while (cur->left) cur = cur->left; // 让cur指向右子树的左下角
            cur->left = root->left; // 将要删除节点的左子树嫁接到右子树的左下角
            
            // 移除要删除的节点，此时要删除的节点左为空右不为空，因为直接向上返回其右孩子即可
            return root->right;
        }
    }
    
    // 单层递归
    // 二叉搜素树确定了搜索的方向
    // root的左子树在删去节点后，左子树的新根节点嫁接到root->left上
    if (key < root->val) root->left = delete(root->left, key); 
    // root的右子树在删去节点后，右子树的新根节点嫁接到root->left上
    if (key > root->val) root->right = delete(root->right, key);
    return root; // 看似没有处理root，但实际上已经在终止条件中处理了
}

上述代码不算复杂，但是很难想。注意：删除节点的操作是通过返回值来进行的，然后让本层递归的上一层去接住本层递归的返回值。本题也可以用迭代法实现。本题的进阶版本：在一般的二叉树中删除节点，更难。吃透本题即可。

本题精简的注释版本如下所示：

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
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // 终止条件，分为五种情况
        // 情况1：找不到要删除的节点
        if (root == NULL) return NULL;

        if (root->val == key)
        {
            // 情况2，要删除的节点左右都为空
            if (root->left == NULL && root->right == NULL) return NULL;
            // 情况3，要删除的节点左为空右不空
            else if (root->left == NULL && root->right) return root->right;
            // 情况4，要删除的节点左不空右为空
            else if (root->left && root->right == NULL) return root->left;
            // 情况5，要删除的节点左不空右不空
            else
            {
                TreeNode* cur = root->right;
                while (cur->left) cur = cur->left;
                cur->left = root->left;
                return root->right;
            }
        }
        
        // 单层递归逻辑
        if (root->val > key) root->left = deleteNode(root->left, key);
        else root->right = deleteNode(root->right, key);
        return root;
    }
};

心得与备忘录

235. 二叉搜索树的最近公共祖先

  1. 本题和236的区别在于，本题的条件得到了强化，不仅是二叉树，而且是二叉搜索树。
  2. 由于二叉搜索树的方向性，本题不需要回溯，自上往下查找目标区间即可。
  3. 本题的核心思路：从上往下遍历二叉树，若当前节点的值大于p和q节点的值，则p和q的最近公共祖先在当前节点的左子树中，从当前节点开始向左遍历。若当前节点的值小于p和q节点的值，则p和q的最近公共祖先在当前节点的右子树中，从当前节点开始向右遍历。若当前节点的值在[p->val, q->val]的范围内，则当前节点就是p和q的最近公共祖先。注意区间是左闭右闭，因为存在p为q的父节点的情况。
  4. 为什么当前节点的值在[p->val, q->val]的范围内，就可以确定当前节点就是p和q的最近公共祖先，而不仅仅是一个普通的公共祖先？这个原因在于：当前节点的值>p->val，则说明p在当前节点的左子树中；当前节点的值<q->val，则说明q在当前节点的左子树中。因此若从当前节点开始向下移动到下一个节点处，那么不是错过p就是错过q。因此当前节点就是p和q的最近公共祖先。
  5. 因为二叉搜索树的有序性，本题的迭代写法也非常简单，甚至比递归解法更简单。

701.二叉搜索树中的插入操作

  1. 本题可以采用递归法和迭代法。但递归法的代码较为简单，因此推荐使用递归法。迭代法的代码略微复杂，但采用的双指针思路也非常清晰，因此也可以掌握迭代法。
  2. 插入新节点的方式有多种，得到的二叉搜索树不唯一。但必然可以在二叉搜索树的叶子节点处插入新的节点。因此不用改变二叉搜索树的结构，就可以实现插入操作。这是本题简单易解的根本所在。

  3. 本题递归法的思路：

    • 递归函数的返回值：返回插入新节点后二叉搜索树的根节点。也可以返回空，但那样写比较麻烦。
    • 终止条件：root节点为空时，说明输入的二叉树为空，因此直接返回val节点即可。
    • 单层递归逻辑：若val > root->val，说明val节点应该被插入在root节点的右子树中，因此有root->right = insert(root->right, val)（insert(root->right, val)返回了root的右子树在插入新节点后的头节点，用root的右节点指向该头节点即可）。若val < root->val，说明val节点应该被插入在root节点的左子树中，因此有root->left = insert(root->left, val)。最终返回root即可。

  4. 卡尔相当于是从叶子节点开始，自下往上讲解递归法的原理。我的理解方式是从root节点开始，自上而下的理解递归的思路。我的理解方式要简单一些，有利于快速写出本题的递归版本的代码。

  5. 本题的迭代写法思路也非常清晰。迭代法采取的是双指针的思路，需要两个节点，一个是cur节点，其是遍历二叉搜索树时的当前节点。另一个是parent节点，其是当前节点的上一个节点（父节点）。我在初次尝试中实现的迭代法代码复杂且由于要考虑多种情况，非常容易写错。因此建议如果要写迭代法，就采用基于双指针思路的迭代法。

450.删除二叉搜索树中的节点

  1. 本题相比于在二叉搜索树中插入节点，复杂得多，原因是删除二叉搜索树中的节点且保持该二叉树仍为二叉搜索树，会改变二叉搜索树原本的结构。

  2. 本题的第一个难点在于分析出删除一个节点的五种情况。

    • 找不到要删除的节点

    • 要删除的节点的左右子节点均为空

    • 要删除的节点的左空右不空

    • 要删除的节点的左不空右空

    • 要删除的节点的左右均不空

    由于在终止条件中要找到需要删除的节点，因此删除节点的操作也在终止条件中完成。

  3. 本题的第二个难点在于实现第五种情况的代码。我直接附上相应的代码并进行解释：

    1
    2
    3
    4
    TreeNode* cur = root->right;
    while (cur->left) cur = cur->left;
    cur->left = root->left;
    return root->right;

    先找到要删除的节点root，然后让cur指针指向root的右子节点。接着用cur遍历root的右子树，直到cur指向右子树的左下角。将root的左子树嫁接到右子树的左下角，最后返回root的右子节点。以root的右子节点为根节点的二叉树就是一棵二叉搜索树。可以举例子画图理解上述构造二叉搜索树的操作。

  4. 本题的基本原理在于：删除节点的操作是通过返回值进行的，然后让本层递归的上一层去接住本层递归的返回值。

  5. 删除一般的二叉树中的节点要采用另外的算法，因此不要求掌握。
  6. 本题也有迭代写法，需要用到双指针算法，代码也更加复杂，因此不要求掌握。
  7. 按理来说，cpp中需要显式地释放被删除节点占用的内存。但不释放也不会对代码的正常运行造成影响。

发表于 更新于 分类于

链接

530.二叉搜索树的最小绝对差
501.二叉搜索树中的众数
236. 二叉树的最近公共祖先

初次尝试

530.二叉搜索树的最小绝对差

本题虽然是个easy题，但我想不出来怎么做。唯一的思路是双指针，至于怎么递归，按照怎样的顺序，我想不出来。

501.二叉搜索树中的众数

本题显然又要充分利用二叉搜索树的特性：中序遍历二叉搜索树，得到的数组是递增的，统计数组中出现频次最高的元素即可。本题我目前发现了两个需要注意的点：

  1. 出现频次最高的元素可能不止一个，因此需要返回一个数组。
  2. 本二叉搜索树的性质为：左子树中的所有节点小于等于根节点，右子树中的所有节点大于等于根节点。

本题似乎也应该采用双指针的做法。若pre->val和cur->val相等，则cnt数组（用于统计元素值出现的次数）中pre->val的值加1。但这里有两个问题：

  • 节点的值可能为负数，因此不能将节点的值直接映射为数组的下标
  • 若出现次数最多的元素不止一个，该如何返回数组

上述两个问题都不好解决，我直接看卡尔的讲解吧。

236. 二叉树的最近公共祖先

本题比较难，我拿到后没有什么想法，猜测可能要用到回溯。直接看卡尔的讲解。

实现

530.二叉搜索树的最小绝对差

目标：求任意两节点间的最小绝对差。由于是二叉搜索树，用中序遍历会成为一个有序的序列，据此思路尝试解出此题。我独立写出了本题的第一种解法：

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
class Solution {
public:
    vector<int> vec;

    void inorder(TreeNode* root)
    {
        if (root == NULL) return;

        inorder(root->left);
        vec.push_back(root->val);
        inorder(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        inorder(root);

        int min = INT_MAX;
        for (int i = 0; i < vec.size() - 1; i ++ )
        {
            if (min > vec[i + 1] - vec[i]) min = vec[i + 1] - vec[i];
        }

        return min;
    }
};

和98.验证二叉搜索树相同，本题应该也可以用maxvalue法和双指针法。这两种方法本质上都是不用额外的数组，直接在中序遍历时计算两个相邻节点的差值，然后选取最小的差值。现在我来尝试这两种解法。这两种解法我还是想不出来，看卡尔的讲解。

接下来讲解如何在中序遍历时利用两个指针直接得出最小绝对差，而不用把二叉树转变为数组。难点：中序遍历二叉树时前后指针如何移动（控制）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int res = INT_MAX;

TreeNode* pre = NULL;

// 返回二叉树的某一特性或者二叉树节点的某个数值，才需要返回值。本题的情况不需要返回值
// 确切来说，一找到就需要立刻去返回的才需要返回值。需要遍历整棵二叉树且用全局变量来记录返回结果的，函数就不需要返回值
void traversal(TreeNode* cur)
{
    // 终止条件
    if (cur == NULL) return;
    
    // 单层递归逻辑：中序遍历
    traversal(cur->left); // 左
    // 中
    if (pre != NULL) res = min(res, cur->val - pre->val);
    pre = cur;
    traversal(cur->right); // 右
}

移动pre和cur的核心在于：cur由中序遍历来移动，pre由赋值移动。cur是当前节点，pre是当前节点的上一个节点。

根据上述核心代码，我写下了本题的完整代码：

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
class Solution {
public:
    int res = INT_MAX;
    TreeNode* pre = NULL;

    void traversal(TreeNode* cur)
    {
        if (cur == NULL) return;

        // 左
        traversal(cur->left);
        // 中
        if (pre != NULL && cur->val - pre->val < res)
            res = cur->val - pre->val;
        // 也可写作
        // if (pre != NULL) res = min(res, cur->val - pre->val);
        pre = cur;
        // 右
        traversal(cur->right);
    }

    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return res;
    }
};

本题也可以用迭代法，但不推荐。

501.二叉搜索树中的众数

二叉搜索树中可能有重复的元素。众数可能不止一个，因此输出众数的集合。暴力做法：对一棵普通的二叉树，遍历二叉树，用map统计每个元素出现的频次，然后将map转换为vector，对vector进行排序，然后在数组中求众数。

如何利用二叉搜索树的特性去求众数的集合？遍历顺序：中序遍历。中序遍历得到的数组中的所有元素是单调递增的。求众数的具体方法：先遍历一遍二叉树，记录下所有元素出现的最高频率。再遍历一遍二叉树，将出现频率为最高频率的元素放入结果集中。其实可以不遍历两遍二叉树，遍历一遍二叉树即可，需要用到一些代码技巧。

双指针算法的思路：用count来统计当前元素出现的次数。当pre->val == cur->val时，当前元素出现的次数加1。当pre->val != cur->val，则count归一。初始时，pre指向NULL，count指向左叶子节点，count也为一。当count == maxcount时，将当前元素放入结果集中。

这里有个问题：如果不事先遍历一遍二叉树，怎么知道maxcount一定是真正的最高频率？后面的具体代码实现中会处理这个问题。现在开始写具体的代码：

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
TreeNode* pre = NULL;
int count = 0; // 当前元素出现的频率
int maxcount = 0; // 整个二叉树中（已经遍历过的节点）的元素出现的最高频率
vector<int> res; // 结果集

// 遍历整个二叉树，结果放入全局变量中，因此递归函数不需要返回值
void traversal(TreeNode* cur)
{
    // 终止条件
    if (cur == NULL) return;
    
    // 单层的递归逻辑
    // 左
    traversal(cur->left);
    // 中：处理逻辑
    // 统计count
    if (pre == NULL) count = 1; // 双指针的初始位置：pre为NULL，cur指向左叶子节点
    else if (pre->val == cur->val) count += 1; // 当前元素出现的次数+1
    else count = 1; // 双指针指向的节点的值不相等，则count又回到1
    pre = cur; // pre跟随cur移动
    
    // 若当前节点的出现次数等于整个二叉树中元素出现的最大次数，则将其放入结果集中
    if (count == maxcount) res.push_back(cur->val);
    
    // 此时存在问题：maxcount不是真正的maxcount，因此需要代码去更新res数组
    // 实时更新res数组，就不需要遍历两遍二叉树了
    if (count > maxcount) 
    {
        maxcount = count; // 更新maxcount
        // maxcount都被更新了，原先的结果集中的结果全废了，清空res
        res.clear();
        res.push_back(cur->val); // 将当前节点的数值放入结果集中
    }
    
    // 右
    traversal(cur->right);
    
    return;
}

我也写出了遍历两次二叉树的代码，如下所示。需要特别注意的是，getmaxcount后需要重置pre和count。遍历两次二叉树的代码显得很冗余，因为基本相同的逻辑写了两遍。

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 {
public:
    TreeNode* pre = NULL;
    vector<int> res;
    int count = 0;
    int maxcount = 0;

    // 第一次遍历二叉树，得到maxcount
    void getmaxcount(TreeNode* cur)
    {
        if (cur == NULL) return;

        getmaxcount(cur->left);
        // 中节点
        if (pre == NULL) count = 1;
        else if (pre->val == cur->val) count += 1;
        else count = 1;
        pre = cur;
        if (count > maxcount) maxcount = count;

        getmaxcount(cur->right);
    }

    // 第二次遍历二叉树，得到结果集
    void traversal(TreeNode* cur)
    {
        if (cur == NULL) return;

        traversal(cur->left);

        // 中节点
        if (pre == NULL) count = 1;
        else if (pre->val == cur->val) count += 1;
        else count = 1;
        pre = cur;
        if (count == maxcount) res.push_back(cur->val);

        traversal(cur->right);
    }

    vector<int> findMode(TreeNode* root) {
        getmaxcount(root);
        pre = NULL; // getmaxcount后重置pre
        count = 0; // getmaxcount后重置count
        traversal(root);
        return res;
    }
};

本题也可以采用迭代法，基本上是迭代的模板加上递归法对中节点的处理逻辑。但本题推荐掌握递归法即可。

236. 二叉树的最近公共祖先

找两个节点p和q的最近公共祖先。条件：二叉树中所有节点的值都是不同的，二叉树中一定存在p和q。根节点是任何两个节点的公共祖先，所以求公共祖先没有意义，求最近公共祖先才有意义。简单的想法：找到节点p和节点q后，从下往上去遍历，直到找到公共的节点。但对二叉树，一般大家熟悉的是从根节点开始从上往下去遍历，实际上也无法从下往上去遍历，但处理顺序可以是从下往上的。回溯的过程就可以让我们去从下往上地处理结果。具体来说，可以判断某个节点的左子树是否出现过p，右子树是否出现过q，如果都出现了，就将该节点向上返回。看该节点的父节点，若父节点的左子树中没出现p，或者右子树中没出现q，则说明该节点是p和q的最近公共祖先。父节点继续将最近公共祖先节点的值向上返回，直到返回到根节点。

从下往上传递p和q节点的最近公共祖先的逻辑写在回溯过程中。想在回溯过程中达到从下往上处理的效果，一定要用后序遍历。后序遍历是左右中，中：处理逻辑。中的具体处理逻辑：判断某个节点的左子树是否出现过p，右子树是否出现过q。即在终止条件中，如果遇到了p或者q，就往上返回。如果一个节点的左子树的返回值不为空，则左子树中出现了p或者q；如果一个节点的右子树的返回值不为空，则右子树中出现了p或者q。如果当前中节点的左右子树的返回值都不为空，则当前的中节点就是p和q最近的公共祖先。还有一种情况。即p就是q的公共祖先。但本情况的处理逻辑和上面是相同的。

具体的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 返回最近的公共祖先
TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q)
{
    // 终止条件1
    if (root == NULL) return NULL;
    // 终止条件2：遇到节点p或者q，则将它们向上返回
    if (root == p || root == q) return root;
    
    // 单层递归的逻辑：后序遍历
    // 左：可以告诉我们左子树中是否出现过p或者q
    TreeNode* left = traversal(root->left, p, q);
    // 右：可以告诉我们右子树中是否出现过p或者q
    TreeNode* right = traversal(root->right, p, q);
    // 中
    // 左右子树中出现了p和q，则root是最近公共祖先，将root返回
    if (left != NULL && right != NULL) return root;
    // 左子树中没有p和q，右子树为最近公共祖先，则继续将right（即最近公共祖先）向上返回，可以参见下面的实例
    if (left == NULL && right != NULL) return right;
    // 左子树为最近公共祖先，右子树中没有p和q，则继续将left(即最近公共祖先)向上返回，和上面一行代码同理
    if (left != NULL && right == NULL) return left;
    // 左右子树都为空，则return NULL
    else return NULL;
}

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 7, q = 4
Output: 2
Explanation: The LCA of nodes 5 and 1 is 3.

img

以上面的二叉树为例，2的左子树返回7，右子树返回4，则2是最近公共祖先。5的左子树返回空，右子树返回2，2是7和4的最近公共祖先，则将2继续向上返回。

为什么上述代码将另一种情况也包含了？以上图为例，若p=7, q=2，则q就是最近的公共祖先。一旦遇到q就返回，就不继续向下遍历了。最终就将q返回到root节点，作为结果了。因此另一种情况不需要特别考虑。

本题的难点：

  • 回溯的过程可以将结果逐层从下往上返回。
  • 从下往上返回结果需要用到后序遍历。先进行左右子树的判断逻辑，再进行中节点的逻辑。只有左右子树的返回值不为空，才将中节点作为最近公共祖先返回。
  • 可以举实例画图理解本题的回溯过程和后序遍历中节点的处理（返回）逻辑。
  • 情况2的处理逻辑包含于情况1中。

心得与备忘录

530.二叉搜索树的最小绝对差

  1. 遇到二叉搜索树，首先需要注意其在中序遍历后得到的数组是递增的这一特性。
  2. 遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值。
  3. 我之所以一开始没有写出本题的双指针解法，原因在于忘记了如何确定递归函数的返回值。对于本题，需要遍历整棵二叉树且用全局变量来记录返回结果，因此递归函数不需要返回值。
  4. 本题的双指针法的思路和98.验证二叉搜索树相同，但两题的区别在于本题的递归函数没有返回值，而98题的递归函数返回值为bool类型。
  5. 移动pre和cur的核心在于：cur由中序遍历来移动，pre由赋值移动。cur是当前节点，pre是当前节点的上一个节点。

501.二叉搜索树中的众数

  1. 本题虽然是easy难度，但其实是比较难的。
  2. 若是一般的二叉树，而非二叉搜索树，则本题的思路为：首先遍历二叉树，用map统计每个元素出现的次数。然后对map按照value进行排序，将排序后的map的(key, value)中最大的一个（或几个）value对应的key放入结果集中。原理不复杂，但代码实现起来比较麻烦。
  3. 本题是二叉搜索树，因此想要充分利用了其性质的话，肯定要采用中序遍历。本题的核心思路依然是双指针算法。需要一个count来存储当前节点出现的次数，一个maxcount来存储整棵二叉树中出现次数最多的节点出现的次数。如果采用两次遍历的做法，那么需要先遍历一遍二叉树得到maxcount，然后再遍历一遍二叉树，将count == maxcount的节点的值存入结果集中。但实际上，遍历一遍二叉树即可完成上述操作。
  4. 遍历一遍二叉树的做法：初始时，count = 1；pre->val == cur->val时，count += 1；否则，count = 1。若count == maxcount，则将当前节点的值放入结果集中。此时出现问题：maxcount不一定是整棵二叉树出现次数最多的节点出现的次数。可以用一个简单的办法解决这个问题：若count > maxcount，则更新maxcount，清空结果集，然后再往结果集中插入当前节点的值。通过这样的操作，就可以动态地去更新结果集，从而避免了对二叉树的两次遍历。

236. 二叉树的最近公共祖先

  1. 本题需要自下往上处理节点，自然而然想到用回溯的思想。

  2. 后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。因此本题采用后序遍历。

  3. 理解以下的示意图就理解了本题：
    236.二叉树的最近公共祖先1

  4. 本题的代码实际上非常简单而清晰，可以根据代码来理解上面的图片，本题的核心代码为中节点的处理逻辑：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // 终止条件1
    if (root == NULL) return NULL;
    // 终止条件2：遇到节点p或者q，则将它们向上返回，对应于节点6和5将它们自身向节点7返回的过程
    if (root == p || root == q) return root;

    // 单层递归的逻辑：后序遍历
    // 左：可以告诉我们左子树中是否出现过p或者q
    TreeNode* left = traversal(root->left, p, q);
    // 右：可以告诉我们右子树中是否出现过p或者q
    TreeNode* right = traversal(root->right, p, q);
    // 中
    // 左右子树中出现了p和q，则root是最近公共祖先，将root返回，对应于节点7将其自身向节点10返回的过程
    if (left != NULL && right != NULL) return root;
    // 左子树中没有p和q，右子树为最近公共祖先，则继续将right（即最近公共祖先）向上返回
    // 对应于节点10将节点7向节点8返回的过程
    if (left == NULL && right != NULL) return right;
    // 左子树为最近公共祖先，右子树中没有p和q，则继续将left(即最近公共祖先)向上返回，和上面一行代码同理
    if (left != NULL && right == NULL) return left;
    // 左右子树都为空，则return NULL
    else return NULL;

    用文字来描述，本题的关键代码实现了以下功能：

    • 遇到节点p或q，就将其向上返回
    • 某个节点的左右子树中包含p和q，则该节点就是p和q的最近公共祖先，将该节点向上返回
    • 某个节点的左右子节点中的一个的返回值不为空，则说明那个返回值不为空的左/右节点为p和q的最近公共祖先，将该节点进一步向上返回
    • 其他情况下均返回空即可

  5. 还有一种情况，即p是q的父节点，此时遍历到p的父节点时，p的父节点就会向上返回p，而不会继续遍历p和其下面的子树。因此本情况也包含在上述代码的逻辑中。

发表于 更新于 分类于

链接

654.最大二叉树

617.合并二叉树

700.二叉搜索树中的搜索

98.验证二叉搜索树

知识

700.二叉搜索树中的搜索

什么是二叉树搜索树？其根节点要比左子树里所有节点的数值大，根节点要比右子树里所有节点的数值小。同理，左右子树也符合这个规则。二叉搜索树的上述规则确定了遍历顺序（既不是前序，也不是中序、后序），而二叉搜素树的上述规则也让本题的迭代写法特别简单。

if (node != NULL) 可以简写为if (node)。

98.验证二叉搜索树

中序遍历一棵二叉搜索树，得到的数组中的元素是有序的。

初次尝试

654.最大二叉树

本题延续106.从中序与后序遍历序列构造二叉树的思路。步骤可以分为：

  1. 找到nums数组中的最大值，作为root

  2. 找到root在nums中的下标

  3. 将nums按照root分为左数组和右数组

  4. 递归处理左数组和右数组，得到左右子树

我独立写出了以下的代码:

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 Solution {
public:
    TreeNode* traversal(vector<int>& nums)
    {
        // 终止条件：数组为空，构造不出树，返回NULL
        if (nums.size() == 0) return NULL;
        
        // 找到nums数组中的最大值，作为root
        int max = -1;
        for (int i = 0; i < nums.size(); i ++ )
        {
            if (nums[i] > max)
            {
                max = nums[i];
            }
        }
        
        // 找到root在nums中的下标
        int j = 0;
        for (j; j < nums.size(); j ++ ) 
            if (nums[j] == max)
                break;
        
        int rootvalue = nums[j];
        TreeNode* root = new TreeNode(rootvalue);

        // 数组分为左数组和右数组
        vector<int> ml(nums.begin(), nums.begin() + j);
        vector<int> mr(nums.begin() + j + 1, nums.end());
        
        // 递归处理左数组和右数组，得到左右子树
        root->left = traversal(ml);
        root->right = traversal(mr);
        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 0) return NULL;
        else return traversal(nums);
    }
};

617.合并二叉树

对于本题，我也采用前序遍历的方法，独立写出了以下的代码：

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
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 应该采用前序遍历，先中节点，再左节点，再右节点
        // 终止条件
        if (root1 == NULL && root2 == NULL) return NULL;
        else if (root1 == NULL) return root2;
        else if (root2 == NULL) return root1;

        int rootvalue = root1->val + root2->val;
        TreeNode* root = new TreeNode(rootvalue);

        // 左节点
        if (root1->left != NULL && root2->left != NULL)
            root->left = mergeTrees(root1->left, root2->left);
        else if (root1->left != NULL)
            root->left = mergeTrees(root1->left, NULL);
        else if (root2->left != NULL)
            root->left = mergeTrees(NULL, root2->left);
        
        // 右节点
        if (root1->right != NULL && root2->right != NULL)
            root->right = mergeTrees(root1->right, root2->right);
        else if (root1->right != NULL)
            root->right = mergeTrees(root1->right, NULL);
        else if (root2->right != NULL)
            root->right = mergeTrees(NULL, root2->right);

        return root; 
    }
};

由上述代码可知，对左右节点的处理都分了三类讨论，这与终止条件中的三类相对应，这是上述代码可以正确运行的基础。本题应该也可以用层序遍历去做。

700.二叉搜索树中的搜索

哈哈哈这题又给我用前序遍历的写法做出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // 终止条件
        if (root == NULL) return NULL;

        // 前序遍历搜索整棵树
        if (root->val == val) return root; // 中节点
        TreeNode* left = searchBST(root->left, val); // 左节点：在左子树中搜索值为val的节点
        TreeNode* right = searchBST(root->right, val); // 右节点：在右子树中搜索值为val的节点

        if (left != NULL && right == NULL) return left; // 在左子树中找到目标节点，则返回之
        else if (left == NULL && right != NULL) return right; // 在右子树中找到目标节点，则返回之
        return NULL; // 左右子树中都没找到，则返回空
    }
};

本题用层序遍历应该也可以做。层序遍历的写法我也独立写出来了：

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:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL) return NULL;

        queue<TreeNode*> q;
        q.push(root);

        while (q.size())
        {
            TreeNode* node = q.front(); q.pop(); // 取出一个节点
            if (node->val == val) return node; // 判断其是否为目标节点，是，则返回之
            
            // 继续往队列中加入当前节点的非空左右子节点
            if (node->left) q.push(node->left); 
            if (node->right) q.push(node->right);
        }
        
        // 若最后没有找到目标节点，则返回空
        return NULL;
    }
};

98.验证二叉搜索树

本题我觉得应该采用中序遍历，先验证左子树是否符合要求，再验证中节点是否符合要求，最后验证右子树是否符合要求，根据这个思路，我尝试独立写出本题的代码。

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
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // 只有root节点
        if (root->left == NULL && root->right == NULL) return true;
        // 左子树为空
        else if (root->left == NULL)
        {
            if (root->val >= root->right->val) return false;
            else return isValidBST(root->right);
        }
        // 右子树为空
        else if (root->right == NULL) 
        {
            if (root->val <= root->left->val) return false;
            else return isValidBST(root->left);
        }
        // 左右子树都不为空
        else
        {
            if (root->val <= root->left->val || root->val >= root->right->val) return false;
            else
            {
                bool res1 = isValidBST(root->left);
                bool res2 = isValidBST(root->right);
                if (res1 && res2) return true;
                else return false;
            }
        }
    }
};

上述代码分了4种情况讨论：只有root节点；左子树为空；右子树为空；左右子树都不为空。但忽略了一种情况：
当root = [5,4,6,null,null,3,7]时，二叉树如下所示：

1
2
3
4
5
graph TD;
    A((5)) --> B((4))
    A --> C((6))
    C --> F((3))
    C --> G((7))

此时虽然[5, 4, 6]是二叉搜索树，[6, 3, 7]也是二叉搜素树，但[6, 3, 7]中存在元素3小于root的5，因此整体并不是一棵二叉搜索树。这种局部都是二叉搜索树，但整体不是二叉搜索树的情况，在我的代码中并没有进行特判。因此我只能通过77/85个测试样例。这也是本题的坑之所在。直接看卡尔的讲解。

实现

654.最大二叉树

规则：在数组中选取最大的元素作为root，最大元素的左区间用于构造左子树，规则同上；最大元素的右区间用于构造右子树，规则同上。

例如，321605，根据以上规则得到以下的最大二叉树：
img

遍历方式：前序遍历。凡是涉及构造二叉树的题目，都要用到前序遍历。原因：前序遍历顺序是中左右，先构造root节点，再去构造左子树和右子树。

代码实现：

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
// 返回二叉树的root节点
TreeNode* construct(vector<int>& nums)
{
    // 确定递归的终止条件
    // 数组中只有一个元素，则唯一一个元素就是root节点
    // 本题题目中对数组的要求是非空，因此不需要考虑数组为空的情况
    if (nums.size() == 1) 
        return new TreeNode(nums[0]);
    
    // 单层递归的逻辑
    // 中节点的逻辑
    // 找到数组中的最大值和其下标
    int maxvalue = 0;
    int index = 0;
    for (int i = 0; i < nums.size(); i ++ )
        if (nums[i] > maxvalue)
        {
            maxvalue = nums[i];
            index = i;
        }
    
    // 根据最大值定义root节点
    TreeNode* root = new TreeNode(maxvalue);
    
    // 左子树的逻辑
    // 根据index切割原数组，将其分为左右数组
    if (index > 0) // 保证左区间中至少有一个元素
    {
        vector<int> l(nums.begin(), nums.begin() + index); // 左区间，左闭右开
        root->left = construct(l); // 递归构造左子树
    }
    
    // 右子树的逻辑
    if (index < nums.size() - 1) // 保证右区间中至少有一个元素
    {
        vector<int> r(nums.begin() + index + 1, nums.end()); // 右区间，左闭右开
        root->right = construct(r); // 递归构造右子树
    }
    
    return root;
}

上述代码严格按照前序遍历构造二叉树。本代码冗余，且效率低，效率低的原因是每次分割时都构造了两个新的数组。对本代码的优化是每次分割数组时不用构造新的数组，操作下标即可。

还有一个重要问题：左右子树的逻辑中要加上if判断。写不写if关键在于终止条件。终止条件保证了数组中至少要有一个元素，因此在左右子树的逻辑中需要加上if判断，也就是保证左右区间中至少有一个元素。当然在左右子树的逻辑中不写if也可以，那就需要在leetcode的主函数外另写一个函数。

完整的代码如下所示：

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
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // 终止条件
        if (nums.size() == 1)
            return new TreeNode(nums[0]);

        // 前序遍历：中节点
        // 找到root的值和下标
        int max = 0, index = 0;
        for (int i = 0; i < nums.size(); i ++ )
            if (nums[i] > max)
            {
                max = nums[i];
                index = i;
            }
        TreeNode* root = new TreeNode(max);

        // 左节点
        if (index > 0)
        {
            vector<int> l(nums.begin(), nums.begin() + index); // 左区间
            root->left = constructMaximumBinaryTree(l); // 递归构造左子树
        }

        // 右节点
        if (index < nums.size() - 1)
        {
            vector<int> r(nums.begin() + index + 1, nums.end()); // 右区间
            root->right = constructMaximumBinaryTree(r); // 递归构造右子树
        }
        return root;
    }
};

左右子树中不加if判断的写法（关键在于终止条件nums.size() == 0），这也是我在初次尝试中的写法，是最不容易写错的写法。因为思路直接继承自106.从中序与后序遍历序列构造二叉树，且不需要在左右子树处加if判断。推荐这个写法：

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
class Solution {
public:
    TreeNode* construct(vector<int>& nums) {
        // 终止条件
        if (nums.size() == 0)
            return NULL;

        // 前序遍历：中节点
        // 找到root的值和下标
        int max = 0, index = 0;
        for (int i = 0; i < nums.size(); i ++ )
            if (nums[i] > max)
            {
                max = nums[i];
                index = i;
            }
        TreeNode* root = new TreeNode(max);

        vector<int> l(nums.begin(), nums.begin() + index); // 左区间
        vector<int> r(nums.begin() + index + 1, nums.end()); // 右区间
        root->left = construct(l); // 递归构造左子树
        root->right = construct(r); // 递归构造右子树
        
        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.size() == 0) return NULL;
        else return construct(nums);
    }
};

在本写法的基础上进一步进行优化。不在分割数组时创建新的数组，只改变数组的下标。

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:
    TreeNode* construct(vector<int>& nums, int begin, int end) {
        // 终止条件，区间是左闭右开的，因此是begin >= end
        if (begin >= end)
            return NULL;

        // 全部操作下标，不需要操作元素的值
        int index = begin;
        // 从begin + 1开始搜索，i = begin时，index = i = begin，不需要写入循环
        for (int i = begin + 1; i < end; i ++ ) 
            if (nums[i] > nums[index])
                index = i;
        TreeNode* root = new TreeNode(nums[index]);

        // 左节点
        // 左闭右开
        int leftbegin = begin;
        int leftend = index;
        root->left = construct(nums, leftbegin, leftend); // 递归构造左子树

        // 右节点
        int rightbegin = index + 1;
        int rightend = end;
        root->right = construct(nums, rightbegin, rightend); // 递归构造右子树
        
        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // 不需要下面这句话，因为已经在construct函数中通过begin == end处理了nums.size() == 0的情况
        // if (nums.size() == 0) return NULL;
        else return construct(nums, 0, nums.size());
    }
};

本版本代码在处理左右节点时不需要进行if判断，原因是若左右区间为空，在递归调用construct函数时会因为begin == end直接返回NULL，而不会出现直接创建数组写法中的空数组的现象（终止条件中未考虑空数组的情况，因此若数组为空不能触发终止条件，会导致程序报错）。因此我也可以在终止条件中考虑空数组的情况，而不在构建左右子树时加上if判断，代码如下所示：

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:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // 终止条件1
        if (nums.size() == 0) return NULL;
        
        // 终止条件2
        if (nums.size() == 1) return new TreeNode(nums[0]);

        // 前序遍历：中节点
        // 找到root的值和下标
        int max = 0, index = 0;
        for (int i = 0; i < nums.size(); i ++ )
            if (nums[i] > max)
            {
                max = nums[i];
                index = i;
            }
        TreeNode* root = new TreeNode(max);

        // 左节点，不需加if判断，由于有终止条件1
        vector<int> l(nums.begin(), nums.begin() + index); // 左区间
        root->left = constructMaximumBinaryTree(l); // 递归构造左子树

        // 右节点，不需加if判断，由于有终止条件1
        vector<int> r(nums.begin() + index + 1, nums.end()); // 右区间
        root->right = constructMaximumBinaryTree(r); // 递归构造右子树
        return root;
    }
};

617.合并二叉树

将两个二叉树合并为一个二叉树。有相同的节点则将两个节点数值相加，作为新节点。对于一棵树上有而另一棵树上没有的节点，将新的节点补充过来。难点：同时操作两个二叉树。本题使用前序遍历最易理解，顺序是中左右。中序和后序也可，但不太符合直观上合并两棵二叉树的过程。本题也可使用迭代法。接下来写递归的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode* mergeTree(TreeNode* t1, TreeNode* t2)
{
    // 终止条件
    // 遍历到t1树的某个位置为空后，需要返回t2树上相同位置的节点（遍历两树是同步的），这样才能将t2树上的该节点的子树加入到合并后的二叉树中
    // 已经包含了两树都为空的情况
    if (t1 == NULL) return t2;
    if (t2 == NULL) return t1;
    
    // 单层递归逻辑，前序遍历
    // 直接改tree1的结构，而不重新定义一棵二叉树
    t1->val += t2->val; // 中节点
    t1->left = mergeTree(t1->left, t2->left); // 左节点
    t1->right = mergeTree(t1->right, t2->right); // 右节点
    
    return t1; // 返回合并后的二叉树，即t1
}

本题采用中序/后序遍历也可以，把单层递归逻辑的三行代码调整顺序即可。按照前序遍历的思路想即可，这符合我们正常合并二叉树的习惯。本题除了在t1上修改，也可以定义一棵新的二叉树，写法如下：

1
2
3
4
5
6
7
TreeNode* root = new TreeNode(0);

root->val = t1->val + t2->val;
root->left = mergeTree(t1->left, t2->left);
root->right = mergeTree(t1->right, t2->right);

return root;

上述写法空间复杂度是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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 迭代写法
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
        // 终止条件
        if (r1 == NULL) return r2;
        if (r2 == NULL) return r1;

        // 迭代写法，常用队列
        queue<TreeNode*> q;
        q.push(r1); q.push(r2);

        while (q.size())
        {
            TreeNode* n1 = q.front(); q.pop();
            TreeNode* n2 = q.front(); q.pop();

            // n1和n2都不为空
            n1->val += n2->val;

            // 若n1和n2的左子树都不为空，则将它们加入队列中
            if (n1->left != NULL && n2->left != NULL)
            {
                q.push(n1->left);
                q.push(n2->left);
            }

            // 若n1和n2的右子树都不为空，则将它们加入队列中
            if (n1->right != NULL && n2->right != NULL)
            {
                q.push(n1->right);
                q.push(n2->right);
            }

            // 若n1的左子树为空，则将n2的左子树赋到n1上
            if (n1->left == NULL)
                n1->left = n2->left;
            
            // 若n1的右子树为空，则将n2的右子树赋到n1上
            if (n1->right == NULL)
                n1->right = n2->right;
        }
        return r1;
    }
};

700.二叉搜索树中的搜索

在二叉树中找到数值为目标值的节点然后返回。

什么是二叉树搜索树？其根节点要比左子树里所有节点的数值大，根节点要比右子树里所有节点的数值小。同理，左右子树也符合这个规则。二叉搜索树的上述规则确定了遍历顺序，而二叉搜素树的上述规则也让本题的迭代写法特别简单。递归法的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode* search(TreeNode* root, int val)
{
    // 两个终止条件
    if (root == NULL || root->val == val) return root; 
    
    // 单层递归的逻辑
    TreeNode* res = NULL; // res用于存递归函数的返回值
    
    // 根据二叉搜索树的特性，若val < root的值，则向root的左子树中去遍历
    if (val < root->val) res = search(root->left, val);
    // 根据二叉搜索树的特性，若val > root的值，则向root的右子树中去遍历
    if (val > root->val) res = search(root->right, val);
    
    return res;
}

相比于我在初次尝试中的写法，上述写法代码更简洁，效率也更高。因为我在初次尝试中的写法没有利用二叉搜索树的特性，只是单纯地先搜索root节点，再递归搜索root节点的左子树和右子树。而卡尔的写法先搜索root节点，然后根据root->val和val的大小对比，决定是在root节点的左子树中继续搜索还是在其右子树中继续搜索。卡尔的写法并不涉及前中后序，因为二叉搜索树本身的性质已经帮我们确定了遍历的顺序。

本题迭代法的代码也并很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* search(TreeNode* root, int val)
{
    while (root != NULL)
    {
        // 向左子树中搜索
        if (val < root->val) root = root->left;
        // 向右子树中搜索
        else if (val > root->val) root = root->right;
        // 相等，说明找到了目标节点
        else return root;
    }
    return NULL; // 树中无目标节点，则返回空
}

迭代法中搜索的方向也由二叉搜索树的特性决定。上述迭代写法也比我在初次尝试中写的迭代写法更为简洁且效率更高，因为卡尔充分利用了二叉搜索树的特性，知道想要找到目标值应该朝着什么方向走。

98.验证二叉搜索树

判断给定的二叉树是否是二叉搜索树。二叉搜索树的定义：左子树中的所有元素都小于root节点，右子树中的所有元素都大于root节点，左右子树都符合这个规则。中序遍历这棵二叉树，其元素是有序的。例如对以下二叉树：

1
2
3
4
5
6
7
graph TD;
    A[5] --> B[3]
    B[3] --> H[1]
    B[3] --> I[NULL]
    A --> C[10]
    C --> F[6]
    C --> G[11]

按照中序遍历，就是[1, 3, 5, 6, 10, 11]，数组是有序的。验证二叉树是否是二叉搜索树，就是验证中序遍历后得到的数组是否是单调递增的。开始写具体的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isvalid(TreeNode* root)
{
    if (root == NULL) return true; // 空二叉树是二叉搜索树
    
    vector<int> vec; // 存放树中序遍历后的结果
    
    // 中序遍历
    isvalid(root->left); // 左
    vec.push_back(root->val); // 中：将遍历到的元素放入数组中
    isvalid(root->right); // 右
    
    // 判断vec是否有序
}

根据上述思路，我写下了能够运行的代码：

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
class Solution {
public:
    vector<int> vec; // 全局变量，用于存放中序遍历二叉树的结果
    
    // 用于中序遍历二叉树的辅助函数
    void inorder(TreeNode* root)
    {
        if (root == NULL) return;
        inorder(root->left);
        vec.push_back(root->val);
        inorder(root->right);
    }

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

        inorder(root);
        
        // 判断数组是否是单调递增的
        for (int i = 0; i < vec.size() - 1; i ++ )
        {
            if (vec[i + 1] <= vec[i]) return false;
        }
        return true;
    }
};

其实不需要将二叉树转换为数组，可以直接在遍历二叉树的过程中判断元素是否是单调递增的。接下来看如何不使用数组来判断二叉树是否是二叉搜索树。本题也可以用迭代法实现，但主要关注递归法。

代码误区：if (root->val > root->left->val && root->val < root->right->val) return true;。实际上这样写是错误的。因为二叉搜索树要求的是root要大于左子树中的所有值，root要小于右子树中的所有值。这个错误我在初次尝试部分已经讨论过了。

现在开始写不额外定义数组的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// -2^31 <= Node.val <= 2^31 - 1，因此maxval要小于int的最小值，因此maxval要取为long long的最小值
long long maxval = LONG_MIN; 

bool isvalid(TreeNode* root)
{
    if (root == NULL) return true;
    bool left = isvalid(root->left); // 左：左子树是否是二叉搜索树
    
    // 中
    // 若二叉树是二叉搜索树，在中序遍历的情况下，元素是递增的，root->val会持续大于maxval
    // maxval相当于记录了遍历过程中当前节点的前一个节点的数值
    if (root->val > maxval)
    {
        maxval = root->val; // 更新maxval
    }
    // 若元素不是递增的，则return false
    else return false;
    
    // 右：右子树是否是二叉搜索树
    bool right = isvalid(root->right);
    
    return left && right; // 要求左右子树同时符合条件
}

以二叉树为例：

1
2
3
4
5
6
7
graph TD;
    A[5] --> B[3]
    B[3] --> H[1]
    B[3] --> I[NULL]
    A --> C[10]
    C --> F[6]
    C --> G[11]

在判断6是否合法时，拿5（root，也是maxvalue）和6进行比较了，因此不会进入初次尝试中提到的误区。若左叶子为INT_MIN，且maxval = INT_MIN，则root->val == maxval，就会直接返回false。因此要让maxval小于INT_MIN。

上述方法存在问题，若左叶子为LONG_MIN（改变输入节点数值的范围），则maxval就无法取更小的值了。我们可以对上述方法进行优化，不额外定义一个变量，而是直接让二叉树的前一个节点和后一个节点进行比较。写下如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* pre = NULL; // pre记录当前节点的前一个节点, root可以和pre进行比较

bool isvalid(TreeNode* root)
{
    if (root == NULL) return true;
    
    bool left = isvalid(root->left); // 左
    // 中
    if (pre != NULL && pre->val >= root->val) return false; // 前一个节点的值大于当前节点，则return false
    pre = root; // 将pre从NULL移到root，即从前一个节点移到当前节点
    bool right = isvalid(root->right); // 右
    
    return left && right;
}

以上方法被称为双指针优化。其实原理非常简单，就是在中序遍历的过程中一直去判断root（当前节点）和pre（前一个节点）之间的大小关系。root指针是由中序遍历的过程去移动的，pre指针是通过直接赋值去移动的。本题是二叉搜索树中的基础题。

心得与备忘录

654.最大二叉树

  1. 本题的思路和106.从中序与后序遍历序列构造二叉树的思路非常类似，理解了那题就可以顺畅的写出本题的代码。

  2. 本题的单层递归核心逻辑如下：

    1. 找到nums数组中的最大值，作为root

    2. 找到root在nums中的下标

    3. 将nums按照root分为左数组和右数组

    4. 递归处理左数组和右数组，得到左右子树

  3. 本题的终止条件可以写两个也可以写一个。若只有终止条件：if (nums.size() == 1) return new TreeNode(nums[0]);，则需要在构造左右子树时加上if判断，保证左右区间不为空。若再加上终止条件：if (nums.size() == 0) return NULL;，则就不需要在构造左右子树时加上if判断了。加上第二个终止条件的原因并非是为了防止传入的nums数组为空（题目限制了传入的数组中至少有1个元素），而是为了在递归时出现数组为空的情况下顺利退出递归过程。

  4. 在实现中，给出了本题的4种写法。写法1和写法4的区别在于：1有1个终止条件，有if判断。4有2个终止条件，无if判断。最推荐的写法（初学者不易写错，且可直接由106演化而来）是写法2。效率最高的写法是写法3（只操作数组下标，而不新建数组，也不操作数组中的元素）。我将在下面附上写法2的代码。

    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:
        TreeNode* construct(vector<int>& nums) {
            // 终止条件
            if (nums.size() == 0)
                return NULL;

            // 找到root的值和下标
            int max = 0, index = 0;
            for (int i = 0; i < nums.size(); i ++ )
                if (nums[i] > max)
                {
                    max = nums[i];
                    index = i;
                }
            TreeNode* root = new TreeNode(max);

            vector<int> l(nums.begin(), nums.begin() + index); // 左区间
            vector<int> r(nums.begin() + index + 1, nums.end()); // 右区间
            root->left = construct(l); // 递归构造左子树
            root->right = construct(r); // 递归构造右子树
            
            return root;
        }

        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            if (nums.size() == 0) return NULL;
            else return construct(nums);
        }
    };

  5. 本题的优化写法是只操作下标，不新建数组，也不操作数组中元素的值。这样可以降低时间和空间复杂度（我感觉时间复杂度基本没变，但空间复杂度由于不需要新建数组，大大降低了）。注意区间始终要保持左闭右开（基于循环不变量原则）。

617.合并二叉树

  1. 本题虽然涉及到同时操作两棵二叉树，但代码的思路和实现都非常简单。
  2. 本题的递归写法的思路：
    • 终止条件：若一棵树的root节点为空，则返回另一棵树的root节点
    • 单层递归：前序遍历。先合并中节点的值，然后再递归处理左子树和右子树。在树1的基础上，将树1修改为合并后的树。也可定义一棵新的树作为合并后的树。
  3. 本题的迭代写法较为复杂，没必要掌握。

700.二叉搜索树中的搜索

  1. 通过本题可以了解二叉搜索树的性质：其根节点要比左子树里所有节点的数值大，根节点要比右子树里所有节点的数值小。同理，左右子树也符合这个规则。二叉搜索树的上述规则确定了遍历顺序（既不是前序，也不是中序、后序），而二叉搜素树的上述规则也让本题的迭代写法特别简单。
  2. 我在初次尝试中的递归写法和迭代写法并没有利用二叉搜索树的性质，因此代码较长且运行效率较低，相当于初次尝试中的代码是执行了在一般的二叉树中搜索节点的过程。而在实现中卡尔的递归写法和迭代写法则充分利用了二叉搜索树的性质，因此代码较为简洁且运行效率高。
  3. 本题的迭代写法尤其简单，原因是：一般二叉树遍历的迭代法，需要使用栈来模拟深度遍历，使用队列来模拟广度遍历。但对于二叉搜索树，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
  4. 本题推荐的写法是卡尔的写法，因为充分利用了二叉搜索树的性质。但如果想不起来卡尔的写法，或者题目中的二叉树并非二叉搜索树，而是一般的二叉树，我在初次尝试中的两种写法不失为一种具有普适性的写法。

98.验证二叉搜索树

  1. 本题的递归解法有三个版本，分别是直接判断中序遍历得到的数组是否递增、maxvalue法和双指针法。其中最简单最直观的方法是方法1，但其也是效率最低的。因此一定要掌握方法1，接着尽力掌握方法3，最后掌握方法2即可。
  2. 本题利用的基本原理：中序遍历一棵二叉搜索树，得到的数组中的元素是有序（递增）的。
  3. maxvalue法和双指针法本质都是在中序遍历二叉树的过程中，不用额外的数组去存储二叉树中的所有元素，而是直接判断当前节点是否大于前一个节点。但maxvalue法具有maxvalue的初始值必须小于节点的最小值的问题，因此若节点的最小值可以取到long long的最小值，则maxvalue的初始值无法确定（cpp不提供超出long long范围的整数类型）。因此双指针法更为完美。
  4. maxvalue法和双指针法在代码实现上略有区别。二者的单层递归逻辑都是中序遍历，但在对中节点的处理逻辑上有差异。maxvalue法是当元素递增时，更新maxvalue的值，否则返回false。双指针法则是当元素不是递增时，返回false，否则更新pre指针。
  5. 本题的迭代解法要用到栈，代码也比较复杂，不要求掌握。

发表于 更新于 分类于

链接

513.找树左下角的值
112. 路径总和，113. 路径总和ii
106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树

知识

106.从中序与后序遍历序列构造二叉树

vector<int> lm(inorder.begin(), inorder.begin() + i);创建了一个左闭右开的区间。在C++中，std::vector的这个构造函数接受两个迭代器作为参数，分别表示要复制的范围的开始和结束。这个范围遵循左闭右开的原则，即包括开始位置的元素，但不包括结束位置的元素。

注意：不可以写作vector<int> lm(0, i)。传入数字的功效和传入迭代器的功效是完全不同的，传入数字的写法无法运行出正确的结果。只有传入两个迭代器的写法是表示创建了一个左闭右开的区间。

初次尝试

513.找树左下角的值

拿到本题后，我先复习了层序遍历的代码，然后先拿层序遍历法尝试一下。本题果然可以简单地用层序遍历解决：

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
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            vector<int> 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.back().front();
        vector<int> ans = res.back();
        return ans.front();
    }
};

现在尝试用递归做本题。首先需要考虑前/中/后序遍历。发现确实不好写，不知道该采用怎样的遍历顺序，且终止条件也不知道该怎么写，直接看卡尔的讲解。

112. 路径总和

本题用层序遍历肯定不好做，因为涉及到从root节点到叶子节点。我尝试用递归解决本题。本题肯定涉及到回溯，搜索完一条root节点到叶子节点的和之后，若没找到targetSum，还需要返回root节点，寻找到新的叶子节点的路径。我不会做此题，直接看卡尔的讲解。

113. 路径总和ii

本题我尝试用112的方法独立完成，但是没有成功，其实我写的代码离能成功运行的代码已经很接近了，思路没错就是部分细节不对。本题的方法应该和112相同，但代码实现上会复杂一些。

106.从中序与后序遍历序列构造二叉树

本题是二叉树中的难题，我没有什么思路，直接来看卡尔的视频。

105.从前序与中序遍历序列构造二叉树

本题的核心思路和106完全一致，我独立写出了本题的代码。

实现

513.找树左下角的值

树左下角的值：树的最后一行最靠左侧的值（不一定是左孩子）。本题用层序遍历（迭代法）最合适，目标值就是最后一层的第一个值。本题用迭代法比用递归法更简单直观。现在主要讲解递归法。

如何用递归法找到树左下角的值？深度最大的叶子节点一定在最后一行。因为本题不需要处理中节点，只需要先遍历左节点即可，因此本题使用前中后序遍历都可。只要保证先遍历左节点，且得到的是深度最大的节点，找到的就是最后一行最靠左侧的节点。现在开始写代码：

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
// 记录二叉树最大深度的全局变量
int maxDepth = INT_MIN; // 初始化为int中的最小值
int res; // 若当前深度大于maxDepth，则更新res为当前节点的值

// depth用于记录当前遍历的节点的深度
void traversal(TreeNode* root, int depth)
{
    // 终止条件：遍历到叶子节点
    if (root->left == NULL && root->right == NULL) 
    {
        // 若当前深度大于maxDepth，则更新res为当前节点的值
        if (depth > maxDepth) 
        {
            maxDepth = depth;
            res = root->val;
        }
    }
  
    // 单层递归的逻辑，前中后序遍历皆可，本题不需要中节点的处理逻辑
    // 左节点
    if (root->left)
    {
        depth ++ ;
        traversal(root->left, depth); // 递归
        depth -- ; // 回溯，即回退到左节点的父节点，然后遍历父节点的右节点，不回溯则会一直向左遍历
        // 以上三行代码可以简写为traversal(root->left, depth + 1)
        // 因为depth + 1并没有改变depth的值，相当于在traversal中+1，在traversal之后复原
    }
  
    // 右节点
    if (root->right)
    {
        depth ++ ;
        traversal(root->right, depth);
        depth -- ;
    }
}

本题的递归解法同样显示地展现了回溯。根据上述核心代码，我写出了本题递归解法的完整代码：

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 Solution {
public:
    int maxDepth = INT_MIN; // 直接int maxDepth = 0也可以
    int res;

    void traversal(TreeNode* root, int depth)
    {
        // 终止条件，遍历到叶子节点
        // 若当前深度大于最大深度，则需要更新最大深度和结果
        if (root->left == NULL && root->right == NULL)
        {
            if (depth > maxDepth)
            {
                res = root->val;
                maxDepth = depth;
            }
        }

        // 单层递归的逻辑
        // 左节点
        if (root->left)
        {
            depth ++ ;
            traversal(root->left, depth);
            depth -- ;
        }

        // 右节点
        if (root->right)
        {
            depth ++ ;
            traversal(root->right, depth);
            depth -- ;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 1); // root节点的深度一般被规定为1，当然规定为0也可以
        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
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;

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

        int res;
        while (q.size())
        {
            int size = q.size();

            for (int i = 0; i < size; i ++ )
            {
                TreeNode* node = q.front();
                q.pop();
                if (i == 0) res = node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return res;
    }
};

112. 路径总和

题意：有无从root节点到叶子节点的一条路径，路径上所有元素之和等于目标和。推荐使用递归法。本题使用前中后序遍历皆可，因为不涉及中节点的处理逻辑，因此中节点放在哪里都可以。规则看似简单，但代码不好写。现在开始写代码：

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
// 返回值为bool类型，找到一条符合条件的路径，立即从下（叶子节点）往上（根节点）返回true
// cnt：计数器，在主函数中传入目标值
// 如果传入0，从上往下遍历每遍历到一个节点就加上这个节点的值，看遍历到叶子节点时cnt是否等于target，这样代码更复杂，不如直接传入target，每次遍历到一个节点就在target中减去该节点的值，看到叶子节点时cnt是否为0
bool traversal(TreeNode* node, int cnt) 
{
    // 终止条件：遇到叶子节点且cnt=0
    if (node->left == NULL && node->right == NULL && cnt == 0) return true;
    if (node->left == NULL && node->right == NULL && cnt != 0) return false;
  
    // 单层递归逻辑
    // 左节点
    if (node->left)
    {
        cnt -= node->left->val; // 从cnt中减去左节点的值
        // 若返回true，则说明node的左孩子到叶子节点的路径中有符合题目要求的路径
        // 此时目标值为cnt -= node->left->val
        // 此时应该继续向上返回true，这样才能一层层将true的结果返回给根节点
        if (traversal(node->left, cnt)) return true;
        // 回溯，遍历到叶子节点后，需要回退到根节点去遍历一条新的路径，因此需要回溯
        // 若不回溯，则cnt一直做减法，则遍历完左子树后，遍历右子树时根本不可能找到符合条件的路径
        cnt += node->left->val;
    }
  
    // 右节点，逻辑同上
    if (node->right)
    {
        cnt -= node->right->val;
        if (traversal(node->right, cnt)) return true;
        cnt += node->right->val;
    }
    // 一直不return true, 则return false
    return false;
}

以上代码没有对中节点的处理逻辑，因此前中后序都可以。对左右节点的处理逻辑可以简写为一句话，我以左节点为例：if (traversal(node->left, cnt -= node->left->val)) return true;，但不建议这样写，因为无法清晰地看到回溯的逻辑。

本题的完整代码如下所示：

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:
    bool traversal(TreeNode* node, int cnt)
    {
        // 终止条件：遍历到叶子节点
        if (node->left == NULL && node->right == NULL && cnt == 0)
            return true;
        // if (node->left == NULL && node->right == NULL && cnt != 0)
        //     return false;
      
        // 左节点
        if (node->left)
        {
            cnt -= node->left->val;
            if (traversal(node->left, cnt)) return true;
            cnt += node->left->val;
        }

        // 右节点
        if (node->right)
        {
            cnt -= node->right->val;
            if (traversal(node->right, cnt)) return true;
            cnt += node->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        return traversal(root, targetSum - root->val);
    }
};

113. 路径总和ii

本题由于要遍历整棵树，找到所有路径，因此递归函数不要返回值，遍历完整棵树后，在函数外定义好的 path和 res中自然会被递归函数写入应有的结果。如果只是要找树中符合条件的一条路径，那么递归函数就要返回值，一旦遍历到叶子节点时找到了合适的路径，就立即返回true，要是一直找不到符合条件的路径，再返回false。

本题的代码相较于上一题要复杂一些，但核心思路其实是相同的。以下几点是与112的主要差异。

  • 首先定义一个 vector<int> path来存放一条符合条件的路径，再定义一个 vector<vector<int>> res来存放树中所有符合条件的路径。
  • 在针对左右节点的操作中，需要回溯，但与112不同的是，本题中的回溯不仅需要回溯 cnt，还需要回溯 path中的元素（先将左右节点放入path中，回溯时又从path中弹出左右节点）。
  • 由于本题的递归函数没有返回值，因此只需要返回空即可，即 return;。
  • 本题需要在主函数中在path中事先插入根节点的值，作为启动的引线（可以想想极端情况，树中只有一个节点，即根节点，如果不在path中事先插入根节点的值，那么即使根节点的值等于 targetSum，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
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
  
    // 本题的递归函数不需要返回值
    void traversal(TreeNode* node, int cnt)
    {
        if (node->right == NULL && node->left == NULL && cnt == 0) 
        {
            res.push_back(path);
            return;
        }

        if (node->right == NULL && node->left == NULL) return;

        // 左节点
        if (node->left)
        {
            path.push_back(node->left->val);
            cnt -= node->left->val;
            traversal(node->left, cnt); // 递归
            path.pop_back(); // 回溯
            cnt += node->left->val; // 回溯
        }

        // 右节点
        if (node->right)
        {
            path.push_back(node->right->val);
            cnt -= node->right->val;
            traversal(node->right, cnt); // 递归
            path.pop_back(); // 回溯
            cnt += node->right->val; // 回溯
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return res;
        path.push_back(root->val); // 事先把根节点放进路径

        traversal(root, targetSum - root->val);
        return res;
    }
};

106.从中序与后序遍历序列构造二叉树

任务：从中序和后序数组中构造出一棵唯一的二叉树。思路：如何用两个数组构造二叉树？
中序：左中右，例：9 3 15 20 7
后序：左右中，例：9 15 7 20 3
由于需要确定根节点，根节点是中节点，而根据中序数组无法确定出根节点的位置，这时就需要后序数组。后序数组的最后一个元素一定是中节点，也就是根节点。以上述两数组为例，根节点就是3。

1
2
graph TD;
    A[3]

再看中序数组，root是3，则左节点是9，右节点是15，20，7。这一步操作就是利用后序数组中找到的root节点在中序数组中完成切割的任务。

1
2
3
graph TD;
    A[3] --> B[9];
    A --> C[x];

再利用中序数组中切割出的两部分在后序数组中完成切割。由上一步知，左节点是9，右节点是15，20，7。结合后序数组知，右节点是15，7，20。右节点中最后一个元素是20，因此20是右子树的中节点。

1
2
3
graph TD;
    A[3] --> B[9];
    A --> C[20];

再利用后序数组去切割中序数组。20是右子树的中节点，中序数组中的右区间为15，20，7，因此左节点是15，右节点是7。

1
2
3
4
5
graph TD;
    A[3] --> B[9];
    A --> C[20];
    C --> F[15];
    C --> G[7];

关键：先通过后序数组找到root节点，再利用root节点切割中序数组，再利用中序数组切割出的左右区间切割后序数组，交替进行。可以具体为以下六步：

  1. 后序数组为空，说明无root节点，返回空的树
  2. 后序数组最后一个元素作为root
  3. 寻找中序数组中root的位置作为切割点
  4. 切割中序数组，切为左右区间
  5. 根据切割中序数组得到的左右区间切割后序数组
  6. 递归处理，构造下一层子树

现在开始写本题的伪代码（注重整体思路而非细节）：

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
// 确定递归函数的参数和返回值
// 返回值：二叉树的根节点
TreeNode* traversal(vector<int> inorder, vector<int> postorder)
{
    // 终止条件：后序数组为空
    if (postorder.size() == 0) return NULL;
  
    // 后序数组的最后一个元素为root节点的值
    int rootvalue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootvalue);
  
    // 优化：若postorder中只有一个元素，则该元素必为叶子节点（root节点也是叶子节点）
    if (postorder.size() == 1) return root;
  
    // 单层递归的逻辑
    // 寻找中序数组中root的位置作为切割点
    int i;
    // 返回中序数组中root的index
    for (i = 0; i < inorder.size(); i ++ )
    {
        if (inorder[i] == rootvalue)
            break; 
    }
  
    // 根据root切中序数组，得到一个左中序数组和一个右中序数组
    // 切后序数组，拿上一步得到的左中序数组来切出后序数组的左区间和右区间，得到一个左后序数组和一个右后序数组
    // 递归处理左区间和右区间，即递归构建root的左右子树
    root->left = traversal(左中序, 左后序);
    root->right = traversal(右中序, 右后序);
    return root;
}

注意：

  • 切中序数组和切后序数组时需要有统一的区间定义。要么都坚持左闭右开，要么都坚持左闭右闭。
  • 先切中序数组，再切后序数组。因为中序数组中的左区间和后序数组中的左区间一定相同。
  • 建议debug时打印切中序数组得到的左中序和右中序数组，打印切后序数组的左后序和右后序数组。

中序和前序数组也可以唯一地确定一棵二叉树。前序数组是中左右，拿着前序数组的第一个元素，即为root元素，拿去切中序数组。剩下的思路是相同的。

中序和后序数组可以唯一地确定二叉树，中序和前序数组也可以唯一地确定二叉树，但后序和前序数组不能唯一地确定二叉树。原因：前序数组和后序数组都可以直接知道root在哪里，但前序和后序数组的左右区间的分割点我们找不到。中序数组的重要性在于其把左右区间给分隔开了。举例：

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

对以上二叉树，前序数组：123，后序数组：321

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

对以上二叉树，前序数组：123，后序数组：321
虽然两棵二叉树的前序数组和后序数组完全一致，但这两棵二叉树完全不同，因此仅靠前序和后序数组不能唯一地确定二叉树。

本题是二叉树中的难题、复杂题，需要经常复习。以上笔记cover了易错点。

根据上述原理，我写出了以下代码：

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
class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder)
    {
        if (postorder.size() == 0) return NULL;

        int rootvalue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootvalue);
        if (postorder.size() == 1) return root;

        // 找到inorder中root的下标
        int i;
        for (i = 0; i < inorder.size(); i ++ )
        {
            if (inorder[i] == rootvalue)
                break;
        }

        // 将inorder根据i分为左中数组和右中数组
        vector<int> lm;
        vector<int> rm;
        for (int j = 0; j < i; j ++ ) 
        {
            lm.push_back(inorder[j]); 
            cout << inorder[j] << ' '; // 打印lm数组中的所有元素
        }
        cout << endl;
        for (int j = i + 1; j < inorder.size(); j ++ ) 
        {
            rm.push_back(inorder[j]); 
            cout << inorder[j] << ' '; // 打印rm数组中的所有元素
        }
        cout << endl;

        postorder.resize(postorder.size() - 1);

        // 将postorder根据上一步的结果分为左后数组和右后数组
        vector<int> lb;
        vector<int> rb;
        for (int l = 0; l < lm.size(); l ++ ) 
        {
            lb.push_back(postorder[l]); 
            cout << postorder[l] << ' '; // 打印lb数组中的所有元素
        }
        cout << endl;
        for (int l = lm.size(); l < postorder.size(); l ++ ) 
        {
            rb.push_back(postorder[l]); 
            cout << postorder[l] << ' '; // 打印rb数组中的所有元素
        }
        cout << endl;

        root->left = traversal(lm, lb);
        root->right = traversal(rm, rb);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

该代码可以通过201 / 202个测试样例，但有一个测试样例超时了，这就需要对上述代码进行优化。写出上述代码时，我犯了一个错误。在将 postorder根据 inorder的结果分为左后数组和右后数组的过程中，我的第一版代码采用了以下的写法（逻辑：把左中数组的最后一个元素作为分界点，在后序数组中查询之，并以此分界点将后序数组划分为左后数组和右后数组）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> lb;
vector<int> rb;
int value = lm[lm.size() - 1];
int k;
for (k = 0; k < lm.size(); k ++ )
{
    if (postorder[k] == value)
        break;
}
//cout << "k=" << k << endl;
for (int l = 0; l < k; l ++ ) 
{
    lb.push_back(postorder[l]);
    cout << postorder[l] << ' ';
}
cout << endl;
for (int l = k + 1; l < postorder.size(); l ++ ) 
{
    rb.push_back(postorder[l]);
    cout << postorder[l] << ' ';
}
cout << endl;

当左中序数组 lm为空时，int value = lm[lm.size() - 1];会访问 lm[-1]。该元素显然不存在，故会报错：index error。因此不能这样写，应该采用按照左中序数组的元素数量分割后序数组的写法。

我对上述代码进行简易的优化后（将resize函数改为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
class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder)
    {
        if (postorder.size() == 0) return NULL;

        int rootvalue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootvalue);
        if (postorder.size() == 1) return root;

        int i;
        for (i = 0; i < inorder.size(); i ++ )
        {
            if (inorder[i] == rootvalue)
                break;
        }
        vector<int> lm, rm;
        for (int j = 0; j < i; j ++ ) lm.push_back(inorder[j]);
        for (int j = i + 1; j < inorder.size(); j ++ ) rm.push_back(inorder[j]);

        postorder.pop_back();

        vector<int> lb, rb;
        for (int j = 0; j < lm.size(); j ++ ) lb.push_back(postorder[j]);
        for (int j = lm.size(); j < postorder.size(); j ++ ) rb.push_back(postorder[j]);


        root->left = traversal(lm, lb);
        root->right = traversal(rm, rb);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

当然，还有进一步优化的空间，代码也可以写得更为简洁。我写下了如下的代码：

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
class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder)
    {
        // 终止条件1：postorder中为空
        if (postorder.size() == 0) return NULL;
      
        // 终止条件2：postorder中只有一个元素，即为root
        int rootvalue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootvalue);
        if (postorder.size() == 1) return root;
      
        // postorder中的最后一个元素为root，在inorder中找到root的下标
        int i;
        for (i = 0; i < inorder.size(); i ++ )
        {
            if (inorder[i] == rootvalue)
                break;
        }
      
        // 将inorder以root作为分割点分割为左中序数组和右中序数组
        vector<int> lm(inorder.begin(), inorder.begin() + i); // 左中序数组
        vector<int> rm(inorder.begin() + i + 1, inorder.end()); // 右中序数组
      
        // 删去postorder的最后一个元素（即root）
        // 也可写作postorder.resize(postorder.size() - 1);
        postorder.pop_back();
      
        // 将postorder以上一步分割得到的左中序数组分割为左后序数组和右后序数组
        vector<int> lb(postorder.begin(), postorder.begin() + lm.size()); // 左后序数组
        vector<int> rb(postorder.begin() + lm.size(), postorder.end()); // 右后序数组
      
        // 递归构建root的左子树和右子树
        root->left = traversal(lm, lb); // 构建左子树，传入的参数为左中序数组和左后序数组
        root->right = traversal(rm, rb); // 构建右子树，传入的参数为右中序数组和右后序数组

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 中序数组或后序数组为空，则树不存在，返回空
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

代码的运行时间基本可以减半，我觉得主要原因是 vector<int> lm(inorder.begin(), inorder.begin() + i);这种写法的时间复杂度要优于遍历数组然后赋值。

本题的下标索引写法（能大大降低空间复杂度，不需要每层递归产生新的数组，只需要对索引重新赋值即可，本写法的代码逻辑和上面的写法完全一致）：

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
class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder, int inbegin, int inend, int postbegin, int postend)
    {
        if (postend == postbegin) return NULL;
      
        int rootvalue = postorder[postend - 1];
        TreeNode* root = new TreeNode(rootvalue);
        if (postend - postbegin == 1) return root;

        // inorder中找到root
        int i;
        for (i = inbegin; i < inend; i ++ )
        {
            if (inorder[i] == rootvalue)
                break;
        }

        // root分割inorder为左中序数组和右中序数组
        int leftinorderbegin = inbegin;
        int leftinorderend = i;
        int rightinorderbegin = i + 1;
        int rightinorderend = inend;

        // 后序数组删去root
        postend -- ;

        // 将postorder分割为左后序数组和右后序数组
        int leftpostorderbegin = postbegin;
        int leftpostorderend = postbegin + leftinorderend - leftinorderbegin;
        int rightpostorderbegin = postbegin + leftinorderend - leftinorderbegin;
        int rightpostorderend = postend;

        root->left = traversal(inorder, postorder, leftinorderbegin, leftinorderend, leftpostorderbegin, leftpostorderend);
        root->right = traversal(inorder, postorder, rightinorderbegin, rightinorderend, rightpostorderbegin, rightpostorderend);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder, 0, inorder.size(), 0, postorder.size());
    }
};

105.从前序与中序遍历序列构造二叉树

本题的代码思路和上题完全一致，我独立一遍写出了本题的代码：

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
// 本题类似于106：利用中序数组和后序数组构造二叉树
// 本题关键思路：前序数组第一位是root
// 在inorder中查找root
// 以root作为分割点，将inorder分为左中序数组和右中序数组
// 根据上一步结果，将preorder分为左前序数组和右前序数组
// 递归处理左右子树
class Solution {
public:
    TreeNode* traversal(vector<int>& preorder, vector<int>& inorder)
    {
        if (preorder.size() == 0) return NULL;

        int rootvalue = preorder[0];
        TreeNode* root = new TreeNode(rootvalue);
        if (preorder.size() == 1) return root;

        // 在inorder中查找root
        int i;
        for (i = 0; i < inorder.size(); i ++ )
        {
            if (inorder[i] == rootvalue)
                break;
        }

        // 以root作为分割点，将inorder分为左中序数组和右中序数组
        vector<int> lm(inorder.begin(), inorder.begin() + i);
        vector<int> rm(inorder.begin() + i + 1, inorder.end());
      
        // 删去preorder的头元素（即root元素）
        reverse(preorder.begin(), preorder.end());
        preorder.pop_back();
        reverse(preorder.begin(), preorder.end());

        // 根据上一步结果，将preorder分为左前序数组和右前序数组
        vector<int> lf(preorder.begin(), preorder.begin() + lm.size());
        vector<int> rf(preorder.begin() + lm.size(), preorder.end());

        // 递归处理左右子树
        root->left = traversal(lf, lm);
        root->right = traversal(rf, rm);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0 || inorder.size() == 0) return NULL;
        return traversal(preorder, inorder);
    }
};

本题的下标索引写法如下所示。用下标索引写法，本题删去前序数组中的第一个元素（root）就非常简单，只需要 prebegin ++即可。

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:
    TreeNode* traversal(vector<int>& preorder, vector<int>& inorder, int prebegin, int preend, int inbegin, int inend)
    {
        if (prebegin == preend) return NULL;

        int rootvalue = preorder[prebegin];
        TreeNode* root = new TreeNode(rootvalue);
        if (prebegin - preend == 1) return root;

        // inorder中找root
        int i;
        for (i = inbegin; i < inend; i ++ )
        {
            if (inorder[i] == rootvalue)
                break;
        }

        // 用root划分inorder
        int leftinbegin = inbegin;
        int leftinend = i;
        int rightinbegin = i + 1;
        int rightinend = inend;

        // preorder中删去root
        prebegin ++ ;

        // 用划分inorder的结果划分preorder
        int leftprebegin = prebegin;
        int leftpreend = prebegin + leftinend - leftinbegin;
        int rightprebegin = prebegin + leftinend - leftinbegin;
        int rightpreend = preend;

        root->left = traversal(preorder, inorder, leftprebegin, leftpreend, leftinbegin, leftinend);
        root->right = traversal(preorder, inorder, rightprebegin, rightpreend, rightinbegin, rightinend);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0 || inorder.size() == 0) return NULL;
        return traversal(preorder, inorder, 0, preorder.size(), 0, inorder.size());
    }
};

心得与备忘录

513.找树左下角的值

  1. 本题用层序遍历法解决更简单，用递归法解决更麻烦。
  2. 本题的层序遍历解法不需要浪费空间复杂度来存储整棵二叉树中的元素值或者二叉树中某一层的元素值。直接存储每一层最左侧元素的值，然后一层层从上往下遍历即可，最后自然会更新为树左下角的值。
  3. 本题的递归解法的核心在于：保证优先左边搜索，然后记录深度最大的叶子节点，此时得到的节点就是树的最后一行最左边的节点。

  4. 递归三部曲：

    • 确定函数的返回值和传入的参数
      本题可以用全局变量记录树的最大深度和结果，这样traversal函数就不需要返回值，只需要在函数中更新记录结果的全局变量即可。传入的参数为根节点和当前节点的深度。
    • 确定终止条件
      当遍历到叶子节点时，终止。若叶子节点的深度大于最大深度，则更新最大深度和结果。
    • 单层递归逻辑
      前中后序遍历都可以，只需要保证优先遍历左节点即可。注意要显式地回溯，这样遍历完父节点的左节点后才能回到父节点，然后接着遍历父节点的右节点。否则会一直向左遍历。

112. 路径总和

  1. 本题推荐用递归解，因为不需要处理中节点，所以前中后序遍历都可。
  2. 本题的递归函数的返回值为bool类型。因为一旦找到一条符合条件的路径，要立即从下（叶子节点）往上（根节点）返回true，因此递归函数需要返回值。
  3. 本题传入递归函数的参数除去node外，还需要传入cnt。cnt直接是targetSum（确切来说是 targetSum - root->val;），遍历到一个节点就减去该节点的值（从根节点开始遍历，因此传入时就要减去根节点的值），观察遍历到叶子节点时cnt是否为0即可。

  4. 递归三部曲：

    • 确定函数的返回值和传入的参数：返回值bool，传入的参数node和cnt
    • 确定终止条件：遍历到叶子节点且cnt == 0，则返回true

    • 单层递归逻辑

      先处理左节点，首先cnt值减去左孩子的值，然后递归判断左孩子到叶子节点的路径中是否有满足条件的路径，若有，则需要从下往上返回true。然后再回溯，将减去的cnt值加回来。若不回溯，cnt就一直减小，导致右孩子到叶子节点的路径中不可能有满足条件的路径。对右节点的处理也是类似的。

  5. 本题需要特别注意：调用递归函数时，传入的参数是 targetSum - root->val，而不是 targetSum。原因是在递归函数的终止条件中，若二叉树中只有root节点不为NULL，且cnt为零时，就返回true，因此本处的cnt应该已经将root节点的值排除在外了。若cnt不把root节点的值排除在外，则在二叉树只有root节点的情况下，永远不可能返回true，因为cnt不可能为0。

113. 路径总和ii

  1. 本题和112的基本思路完全一致，但应当关注和112的差异，主要有以下5点差异。
  2. 本题需要在函数外先定义一个 vector<int> path来存放一条符合条件的路径，再定义一个 vector<vector<int>> res来存放树中所有符合条件的路径。
  3. 本题的递归函数不需要返回值，112的递归函数需要返回值。具体原因见本题的实现部分。
  4. 由于本题的递归函数不需要返回值，因此本题的递归函数在返回时只需要写 return;。
  5. 在处理左右节点的逻辑中，需要对 cnt操作并将左右节点的值放入 path中，然后再调用递归函数。因此在回溯时，也需要同时恢复 cnt的值和 path数组。
  6. 本题需要在主函数中在path中事先插入根节点的值，作为启动的引线。

106.从中序与后序遍历序列构造二叉树

  1. 本题的具体操作过程可以举一个具体的例子来展现，参见本题的实现部分。

  2. 本题的核心思路在于以下五步：

    • 根据后序数组找到root（后序数组中的最后一位）
    • 在中序数组中查找root的下标
    • 以root为分割点，将中序数组分割为左中序数组和右中序数组
    • 在后序数组中找到与左中序数组相同的一段，即为左后序数组，剩下的后序数组为右后序数组
    • 递归构建root的左右子树（根据左右中序数组和左右后序数组）

  3. 本题的调试方法：打印出左右中序数组和左右后序数组，观察它们是否符合预期

  4. 中序和后序数组可以唯一地确定一棵二叉树，前序和中序数组也可以唯一地确定一棵二叉树，但前序和后序数组不可以唯一地确定一棵二叉树，我在实现部分举出了反例。原因：前序数组和后序数组都可以直接知道root在哪里，但前序和后序数组的左右区间的分割点我们找不到。中序数组的重要性在于其把左右区间给分隔开了。

  5. 本题和下一题的更佳写法是下标索引写法，即每次用下标索引来分割。虽然时间复杂度基本保持不变，但空间复杂度相比于传统写法大大降低了，因为不需要每层递归产生新的数组，只需要对索引重新赋值即可。

  6. 下标索引写法挺容易出错的，特别是在确定左右区间的边界上，搞不定的话就采用简单直接的普通写法。

  7. 我写的下标索引写法，还可以做进一步优化，若将划分postorder的代码：

    1
    2
    3
    4
    int leftpostorderbegin = postbegin;
    int leftpostorderend = postbegin + leftinorderend - leftinorderbegin;
    int rightpostorderbegin = postbegin + leftinorderend - leftinorderbegin;
    int rightpostorderend = postend;

    直接写作：

    1
    2
    3
    4
    int leftpostorderbegin = postbegin;
    int leftpostorderend = postbegin + i - inbegin;
    int rightpostorderbegin = postbegin + i - inbegin;
    int rightpostorderend = postend - 1;

    即将

    1
    2
    3
    4
    5
    postend -- ;
    int leftinorderbegin = inbegin;
    int leftinorderend = i;
    int rightinorderbegin = i + 1;
    int rightinorderend = inend;

    直接代入划分postorder的代码中，时间复杂度可以进一步降低。对于106题的下标索引写法也是如此。

105.从前序与中序遍历序列构造二叉树

  1. 本题的核心思路和上题完全相同，也是在于以下五步：

    • 前序数组第一位是root
    • 在inorder中查找root
    • 以root作为分割点，将inorder分为左中序数组和右中序数组
    • 根据上一步结果，将preorder分为左前序数组和右前序数组
    • 递归处理左右子树
  2. 本题和上题的不同之处在于，上题在分割出左右中序数组后，需要删去后序数组的最后一个元素，即root元素。本题则是在分割出左右中序数组后，需要删去前序数组的第一个元素，即root元素。删去数组的最后一个元素的操作相对简单，只需要 pop_back即可，但删去数组的第一个元素的操作相对复杂。我想到的办法是翻转数组，删去数组最后一个元素，再翻转数组。
  3. 用下标索引写法，本题删去前序数组中的第一个元素（root）就非常简单，只需要 prebegin ++即可。

发表于 更新于 分类于

技术栈

  • 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中，async和await关键字一起使用，作为处理异步操作的一种方式，主要用于替代传统的回调函数和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）操作符。当你在一个对象后面加上?后跟属性名或方法，这意味着如果这个对象存在（即不是null或undefined），则会尝试访问该属性或方法；如果对象是null或undefined，则不会尝试访问该属性或方法，而是直接返回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树相同/相异）。