LYL's Blog
0%

leetcode刷题系列之二叉树

发表于 分类于
本文字数： 40k 阅读时长 ≈ 37 分钟

这篇文章是leetcode刷题系列的第4部分——二叉树。这里把有代表性的题目发出来，共计36道。

leetcode刷题系列其它文章组织如下：

1. 数组

2. 链表

3. 字符串

4. 二叉树

5. 队列和栈

6. 动态规划

7. 数据结构设计

8. 刷题小知识点

114. Binary Tree Preorder Traversal

二叉树的前序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 迭代实现
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> nodes;
    nodes.push(root);
    while(!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        while(node) {
            res.push_back(node->val);
            if(node->right) {
                nodes.push(node->right);
            }
            node = node->left;
        }
    }
    return res;
}
94. Binary Tree Inorder Traversal

二叉树的中序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 正中序遍历, 即左-中-右
vector<int> inorderTraversal(TreeNode* root) {        
    stack<TreeNode*> nodes;
    vector<int> res;
    while(1) {
        while(root) {
            nodes.push(root);
            root = root->left;
        }
        if(nodes.empty()) {
            break;
        }
        root = nodes.top();
        nodes.pop();
        res.push_back(root->val);
        root = root->right;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 逆中序遍历, 即右-中-左
vector<int> inorderTraversal(TreeNode* root) {        
    stack<TreeNode*> nodes;
    vector<int> res;
    while(1) {
        while(root) {
            nodes.push(root);
            // 右子树依次入栈
            root = root->right;
        }
        if(nodes.empty()) {
            break;
        }
        root = nodes.top();
        nodes.pop();
        res.push_back(root->val);
        // 这里去左子树
        root = root->left;
    }
    return res;
}
145. Binary Tree Postorder Traversal

二叉树的后序遍历。

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
// 此解法借鉴中序遍历的思路
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> nodes;
    vector<int> res;
    TreeNode* preVisited = nullptr;
    while(1) {
        while(root) {
            nodes.push(root);
            root = root->left;
        }
        if(nodes.empty()) {
            break; 
        }
        root = nodes.top();
        // 如果待访问节点没有右孩子或者右孩子刚才访问过
        if(root->right == nullptr || root->right == preVisited) {
            // 就访问
            preVisited = root;
            res.push_back(root->val);
            nodes.pop();
            // 这是为了跳过下次的 while(root) 循环
            root = nullptr;
            // 下一个待访问节点一定是刚刚访问节点的父节点
        }
        // 如果待访问节点有右孩子并且右孩子上次没有访问过
        else {
            // 就去访问右孩子
            root = root->right;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 此解法借鉴前序遍历的思路
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> nodes;
    vector<int> res;
    nodes.push(root);
    while(!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        while(node) {
            res.push_back(node->val);
            // 和前序遍历相反的顺序访问左右子树
            if(node->left) {
                nodes.push(node->left);
            }
            node = node->right;
        }
    }
    // 最后, 逆序输出就和后序遍历一样
    reverse(res.begin(), res.end());
    return res;
}
102. Binary Tree Level Order Traversal

二叉树的层序遍历。

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
// 使用队列迭代实现
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    queue<TreeNode*> nodes;
    if(root) {
        nodes.push(root);
    }
    while(!nodes.empty()) {
        int n = nodes.size();
        vector<int> subVector(n);
        for(int i = 0; i < n; i++) {
            root = nodes.front();
            nodes.pop();
            subVector[i] = root->val;
            if(root->left) {
                nodes.push(root->left);
            }
            if(root->right) {
                nodes.push(root->right);
            }
        }
        res.push_back(subVector);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 借助前序遍历的思想, 递归实现
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    // 每次递归的时候提供被遍历节点的层级信息
    auto preOrder = [&](auto&& preOrder, TreeNode* root, size_t level) {
        if(root == nullptr) {
            return;
        }
        level++;
        if(res.size() < level) {
            res.resize(level);
        }
        res[level - 1].push_back(root->val);
        preOrder(preOrder, root->left, level);
        preOrder(preOrder, root->right, level);
    };
    preOrder(preOrder, root, 0);
    return res;
}
104. Maximum Depth of Binary Tree

给定二叉树的根，返回其最大深度。二叉树的最大深度是指沿着从根节点到最远的叶节点的最长路径的节点数。

Example:

img 
1
2
Input: root = [3,9,20,null,null,15,7]
Output: 3
1
2
3
4
5
6
7
// 自底向上递归
int maxDepth(TreeNode* root) {
    if(!root) {
        return 0;
    }
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 自上到下递归
int maxDepth(TreeNode* root) {
    int res = 0;
    // 每次递归时传递被访问节点的深度信息
    function<void(TreeNode*, int)> helper = [&](TreeNode* root, int depth) {
        if(!root) {
            return;
        }
        res = max(res, depth);
        helper(root->left, 1 + depth);
        helper(root->right, 1 + depth);
    };
    helper(root, 1);
    return res;
}
111. Minimum Depth of Binary Tree

给定二叉树的根，返回其最小深度。二叉树的最小深度是指沿着从根节点到最近的叶节点的最短路径的节点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 递归解法
int minDepth(TreeNode* root) {
    if(!root) {
        return 0;
    }
    int leftMinDepth = minDepth(root->left);
    int rightMinDepth = minDepth(root->right);
    if(leftMinDepth == 0) {
        return 1 + rightMinDepth;
    }
    if(rightMinDepth == 0) {
        return 1 + leftMinDepth;
    }
    return 1 + min(leftMinDepth, rightMinDepth);
}
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
// BFS 迭代解法
int minDepth(TreeNode* root) {
    queue<TreeNode*> q;
    if(root) {
        q.push(root);
    }
    int step = 0;
    while(!q.empty()) {
        int sz = q.size();
        while(sz-- > 0) {
            TreeNode* node = q.front();
            q.pop();
            if(!node->left && !node->right) {
                return step + 1;
            }
            if(node->left) {
                q.push(node->left);
            }
            if(node->right) {
                q.push(node->right);
            }
        }
        step++;
    }
    return step;
}
112. Path Sum

给定二叉树的根和一个整数targetSum，如果树具有从根到叶的路径，则沿路径的所有值加起来等于targetSum，则返回true。

Example:

img 
1
2
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 自顶向下递归
bool hasPathSum(TreeNode* root, int sum) {
    if(!root) {
        return false;
    }
    if(!root->left && !root->right) {
        return sum == root->val;
    }
    if(hasPathSum(root->left, sum - root->val)) {
        return true;
    }
    if(hasPathSum(root->right, sum - root->val)) {
        return true;
    }
    return false;
}
113. Path Sum II

给定二叉树的根和一个整数targetSum，返回所有从根到叶的路径，其中每个路径的和等于targetSum。

Constraints:

  • The number of nodes in the tree is in the range[0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Example:

img 
1
2
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
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>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> res;
    vector<int> target;
    function<void((TreeNode*, int))> dfs = [&](TreeNode* root, int sum) {
        if(!root) {
            return;
        }
        sum -= root->val;
        target.push_back(root->val);
        // 如果是叶子节点
        if(!root->left && !root->right && sum == 0) {
            res.push_back(target);
        }
        dfs(root->left, sum);
        // target.pop_back();
        // target.push_back(root->val);
        dfs(root->right, sum);
        target.pop_back();
    };
    dfs(root, sum);
    return res;
}
437. Path Sum III

你将获得一棵二叉树，其中每个节点都包含一个整数值。查找路径中节点值总和为给定值的路径数。

该路径无需在根或叶处开始或结束，但必须向下（仅从父节点到子节点移动）。

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

       10
      /  \
     5   -3
    / \    \
  3   2   11
/ \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
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
// recursive
int pathSum(TreeNode* root, int sum) {
    if(!root) {
        return 0;
    }
    // 等于以从 root 开始的子路径 + ...
    return rootPathSum(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
// dfs 求解以从 root 开始的子路径
int rootPathSum(TreeNode* root, int targetSum) {
    int res = 0;
    function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int curSum) {
        if(root) {
            curSum += root->val;
            // 和上一题 II 不同了
            // 不必等到是叶子节点
            // 只要中间有满足的, 直接增加计数
            if(targetSum == curSum) {
                res++;
            }
            dfs(root->left, curSum);
            dfs(root->right, curSum);
        }
    };
    dfs(root, 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
// 上面纯递归的方法相当于暴力搜索, 时间复杂度为 O(n2)
// 不仅数组中可以用到前缀和, 这里也可以用到, 时间复杂度可以优化到 O(n)
int pathSum(TreeNode* root, int sum) {
    int count = 0;
    unordered_map<int, int> mapping; // <前缀和, 出现的次数>
    // base case
    mapping[0] = 1;
    function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int curSum) {
        if(root) {
            curSum += root->val;
            if(mapping.count(curSum - sum)) {
                count += mapping[curSum - sum];
            }
            mapping[curSum]++;
            dfs(root->left, curSum);
            // mapping[curSum]--;
            // mapping[curSum]++;
            dfs(root->right, curSum);
            mapping[curSum]--;
        }
    };
    dfs(root, 0);
    return count;
}
666. Path Sum IV

对于一棵深度小于5的树，可以用一组三位十进制整数来表示。

对于每个整数：

百位上的数字表示这个节点的深度D，1 <= D <= 4。
十位上的数字表示这个节点在当前层所在的位置P，1 <= P <= 8。位置编号与一棵满二叉树的位置编号相同。
个位上的数字表示这个节点的权值V，0 <= V <= 9。
给定一个包含三位整数的升序数组，表示一棵深度小于5的二叉树，请你返回从根到所有叶子结点的路径之和。

示例 1：

1
2
3
4
5
6
7
8
9
输入: [113, 215, 221]
输出: 12
解释: 
这棵树形状如下:
  3
/ \
5   1

路径和 = (3 + 5) + (3 + 1) = 12.

示例 2：

1
2
3
4
5
6
7
8
9
输入: [113, 221]
输出: 4
解释: 
这棵树形状如下: 
3
 \
  1

路径和 = (3 + 1) = 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
// 类似于堆排序中将完全二叉树存储在一个向量的思路
// 借助一个哈希表来记录二叉树的每个节点在向量中的索引和其权重的映射
// 每个节点的索引可通过其深度和位置计算出来
// 公式为 i = 2 ^ (depth - 1) + position - 1
// 比如, 根节点 112, depth = 1, position = 1, i = 2 ^ (1 - 1) + 1 - 1 = 1
// 某节点 346, depth = 3, position = 4, i = 2 ^ (3 - 1) + 4 - 1 = 7
// 这样表示之后, 索引为 i 的节点
// 其左孩子索引为 2 * i, 右孩子索引为 2 * i + 1
int pathSum(vector<int>& nums) {
    int res = 0;
    unordered_map<int, int> mapping;
    for(int num : nums) {
        int depth = num / 100;
        int position = num % 100 / 10;
        int weight = num % 10;
        mapping[pow(2, depth - 1) + position - 1] = weight;
    }
    function<void(int, int)> dfs = [&](int i, int sum) {
        if(mapping.count(i) == 0) {
            return;
        }
        sum += mapping[i];
        // 到达叶子节点
        if(mapping.count(2 * i) == 0 && mapping.count(2 * i + 1) == 0) {
            res += sum;
        }
        // 去左子树
        dfs(2 * i, sum);
        // 去右子树
        dfs(2 * i + 1, sum);
    };
    dfs(1, 0);
    return res;
}
129. Sum Root to Leaf Numbers

你将获得只包含0到9的数字的二叉树的根。树中的每条从根到叶的路径都代表一个数字。

例如，从根到叶的路径1 -> 2 -> 3表示数字123。返回所有从根到叶的数字的总和。

Constraints:

  • The number of nodes in the tree is in the range[1, 1000].
  • 0 <= Node.val <= 9.
  • The depth of the tree will not exceed 10.

Example:

img 
1
2
3
4
5
6
7
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int sumNumbers(TreeNode* root) {
    int res = 0;
    auto dfs = [&](auto&& dfs, auto* root, int num) {
        if(!root) {
            return;
        }
        num = num * 10 + root->val;
        if(!root->left && !root->right) {
            res += num;
        }
        dfs(dfs, root->left, num);
        dfs(dfs, root->right, num);
    };
    dfs(dfs, root, 0);
    return res;
}
124. Binary Tree Maximum Path Sum

二叉树中的路径是节点序列，其中序列中的每对相邻节点都有一条连接它们的边。 一个节点最多只能出现在序列中一次。 请注意，该路径不需要通过根。路径的路径总和是路径中节点值的总和。

给定二叉树的根，返回任何路径的最大路径总和。

Constraints:

  • The number of nodes in the tree is in the range[1, 3 * 104].
  • -1000 <= Node.val <= 1000.

Example:

img 
1
2
3
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 后序遍历思想
int maxPathSum(TreeNode* root) {
    int res = INT_MIN;
    // 递归函数的定义是返回 [以 root 为首节点] 的最大路径和
    auto dfs = [&](auto&& dfs, auto* root) {
        if(!root) {
            return 0;
        }
        // 如果以 left 或 right 为首节点的路径和为负数
        // 就不加上它
        // 这样就能保证返回的值是以 root 为首节点的最大路径和
        // 就是说将 root 单节点看作一条路径
        int leftMaxSum = max(0, dfs(dfs, root->left));
        int rightMaxSum = max(0, dfs(dfs, root->right));
        // 计算 [经过] root 的最大路径和
        // 这样, 通过递归的过程, 保证会分别计算经过每一个节点的最大路径和
        res = max(res, leftMaxSum + root->val + rightMaxSum);
        return root->val + max(leftMaxSum, rightMaxSum);
    };
    dfs(dfs, root);
    return res;
}
105. Construct Binary Tree from Preorder and Inorder Traversal

给定两个整数数组preorder和inorder，其中preorder是二叉树的前序遍历，而inorder是同一树的中序遍历，构造并返回二叉树。

640 sdsef 
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
// 首先要知道前序遍历的首元素就是树的根
// 其在中序遍历的位置的左边所有元素构成左子树, 右边所有元素构成右子树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = inorder.size();
    auto build = [&](auto&& build, int preStart, int inStart, int inEnd) {
        if(inStart > inEnd) {
            return (TreeNode*)nullptr;
        }
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        // 定位 rootVal 在中序遍历中的位置
        int index = inStart;
        for(; index <= inEnd; index++) {
            if(inorder[index] == rootVal) {
                break;
            }
        }
        // 计算左子树节点数量
        int leftSize = index - inStart;
        root->left = build(build, preStart + 1, inStart, index - 1);
        root->right = build(build, preStart + leftSize + 1, index + 1, inEnd);
        return root;
    };
    return build(build, 0, 0, n - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 可以使用一个哈希表存储节点值在中序遍历数组中的索引
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = inorder.size();
    unordered_map<int, int> mapping;
    for(int i = 0; i < n; i++) {
        mapping[inorder[i]] = i;
    }
    auto build = [&](auto&& build, int rootIndex, int inStart, int inEnd) {
        if(inStart > inEnd) {
            return (TreeNode*)nullptr;
        }
        int rootVal = preorder[rootIndex];
        int index = mapping[rootVal];
        int leftSize = index - inStart;
        TreeNode* root = new TreeNode(rootVal);
        // 左子树的根节点在当前根节点位置 + 1 的位置
        root->left = build(build, rootIndex + 1, inStart, index - 1);
        // 右子树的根节点在当前根节点位置 + 左子树长度 + 1 的位置
        root->right = build(build, rootIndex + leftSize + 1, index + 1, inEnd);
        return root;
    };
    // 因为每次我们只是需要得到节点值在中序遍历数组中的索引
    // 现在我们已经预存储了节点值到索引的映射, 参数中就不需要中序遍历数组了
    // 并且左右树根节点的值在前序遍历数组中的位置可以通过当前根节点的位置和左子树的长度来确定
    return build(build, 0, 0, n - 1);
}
106. Construct Binary Tree from Inorder and Postorder Traversal

给定两个整数数组postorder和inorder，其中postorder是二叉树的后序遍历，而inorder是同一树的中序遍历，构造并返回二叉树。

444 fgfg 
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
// 首先要知道后序遍历的尾元素就是树的根
// 其在中序遍历的位置的左边所有元素构成左子树
// 右边所有元素构成右子树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    int n = inorder.size();
    auto build = [&](auto&& build, int rootIndex, int inStart, int inEnd) {
        if(inStart > inEnd) {
            return (TreeNode*)nullptr;
        }
        // 后序遍历尾元素就是根
        int rootVal = postorder[rootIndex];
        TreeNode* root = new TreeNode(rootVal);
        // 定位根在中序遍历中的位置
        // 一定存在
        // 这里有一个特殊情况 inStart == inEnd
        // 出现这种情况 index 应该等于 inStart == inEnd
        // 递归基可以处理
        int index = inStart;
        for(; index <= inEnd; index++) {
            if(inorder[index] == rootVal) {
                break;
            }
        }
        // 计算右子树的节点数
        int rightSize = inEnd - index;
        // 左子树的根节点在当前根节点位置 - 右子树长度 - 1 的位置
        root->left = build(build, rootIndex - rightSize - 1, inStart, index - 1);
        // 右子树的根节点在当前根节点位置 - 1 的位置
        root->right = build(build, rootIndex - 1, index + 1, inEnd);
        return root;
    };
    return build(build, n - 1, 0, n - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 可以使用一个哈希表存储节点值在中序遍历数组中的索引
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    int n = inorder.size();
    unordered_map<int, int> mapping;
    for(int i = 0; i < inorder.size(); i++) {
        mapping[inorder[i]] = i;
    }
    auto build = [&](auto&& build, int rootIndex, int inStart, int inEnd) {
        if(inStart > inEnd) {
            return (TreeNode*)nullptr;
        }
        int rootVal = postorder[rootIndex];
        int index = mapping[rootVal];
        int rightSize = inEnd - index;
        TreeNode* root = new TreeNode(rootVal);
        // 左子树的根节点在当前根节点位置 - 右子树长度 - 1 的位置
        root->left = build(build, rootIndex - rightSize - 1, inStart, index - 1);
        // 右子树的根节点在当前根节点位置 - 1 的位置
        root->right = build(build, rootIndex - 1, index + 1, inEnd);

        return root;
    };
    // 因为每次我们只是需要得到节点值在中序遍历数组中的索引
    // 现在我们已经预存储了节点值到索引的映射, 参数中就不需要中序遍历数组了
    // 左右树根节点的值在前序遍历数组中的位置可以通过当前根节点的位置和右子树的长度来确定
    return build(build, n - 1, 0, n - 1);
}
889. Construct Binary Tree from Preorder and Postorder Traversal

返回与给定的前序和后序遍历匹配的任意二叉树。二叉树中的值是不同的正整数。

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
// 虽然有些情况不能确定一棵唯一的二叉树
// 但我们决定左右子树的规则固定即可
// 首先注意到前序遍历的首元素为树的根
// 首元素的下一个元素可能为其左子树的根, 也可能为其右子树的根
// 但我们始终把它认定为左子树的根
// 接下来就是在后序遍历中定位到 前序遍历首元素的下一个元素 的位置
// 这个位置左边的就是左子树所有元素 (包括这个位置上的元素, 实际上它是左子树的根)
// 右边的就是右子树所有元素 (除了末元素, 因为它是当前树的根啊)
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post)
{
    int n = pre.size();
    function<TreeNode*(int, int, int, int)> construct = [&](int preStart, int preEnd, int postStart, int postEnd) {
        if(preStart > preEnd) {
            return (TreeNode*)nullptr;
        }
        int rootVal = pre[preStart];
        TreeNode* root = new TreeNode(rootVal);
        // 这个条件判断非常重要
        // 如果 preStart == preEnd
        // 下面的 index 就会因为找不到而很大 为 postEnd
        // 导致错误地计算出很大的 leftSize
        // 这种情况递归基处理不了
        if(preStart == preEnd) {
            return root;
        }
        // 定位到左子树的根在后序遍历中的位置
        // 此时保证至少会有该元素, 也就是说 pre[preStart + 1] 在后序遍历中一定存在
        int index = postStart;
        for(; index < postEnd; index++) {
            if(post[index] == pre[preStart + 1]) {
                break;
            }
        }
        int leftSize = index - postStart + 1;
        root->left = construct(preStart + 1, preStart + leftSize, postStart, index);
        root->right = construct(preStart + leftSize + 1, preEnd, index + 1, postEnd - 1);
        return root;
    };
    return construct(0, n - 1, 0, n - 1);
}
1008. Construct Binary Search Tree from Preorder Traversal

给定一个整数已排序数组，该数组表示二叉搜索树的前序遍历结果，请构造该BST树并返回其根。

可以确保始终可以找到满足测试用例要求的BST。

Constraints:

  • 1 <= preorder.length <= 100.
  • 1 <= preorder[i] <= 108.
  • All the values of preorder are unique.

Example:

img 
1
2
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
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
// 首先可以确定前序遍历的首元素为树的根
// 其左子树的所有元素都小于首元素
// 其右子树的所有元素都大于首元素
// 所以, 我们接下来只要确定数组中第一个大于首元素的值的位置
// 就能够直到左子树和右子树的元素范围
TreeNode* bstFromPreorder(vector<int>& preorder)
{
    int n = preorder.size();
    function<TreeNode*(int, int)> build = [&](int preStart, int preEnd) {
        if(preStart > preEnd) {
            return (TreeNode*)nullptr;
        }
        // 根为首元素
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        // 找到第一个大于首元素的位置
        int index  = preStart + 1;
        for(; index <= preEnd; index++) {
            if(preorder[index] > rootVal) {
                break;
            }
        }
        // 到这里, 有两种情况
        // 1. 左子树为空, 此时 index 应该为 prepreStart + 1
        // 2. 右子树为空, 此时 index 应该为 preEnd + 1
        // 无论哪一种情况, 递归进去之后, 递归基都可以处理
        root->left = build(preStart + 1, index - 1);
        root->right = build(index, preEnd);
        return root;
    };
    return build(0, n - 1);
}
117. Populating Next Right Pointers in Each Node II - LeetCode

填充二叉树的每个节点下一个指针以指向其下一个右节点。 如果没有下一个右节点，则下一个指针应设置为NULL。

最初，所有下一个指针都设置为NULL。

img 
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
/*
struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
};
*/

// 使用辅助节点的迭代式解法
Node* connect(Node* root) {
    Node helper;
    Node* cur = root;
    while(cur) {
        Node* last = &helper;
        while(cur) {
            if(cur->left) {
                last->next = cur->left;
                last = last->next;
            }
            if(cur->right) {
                last->next = cur->right;
                last = last->next;
            }
            cur = cur->next;
        }
        cur = helper.next;
        helper.next = nullptr;
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 使用队列的迭代式解法(层序遍历)
Node* connect(Node* root) {
    Node* cur = root;
    queue<Node*> nodes;
    if(cur) {
        nodes.push(cur);
    }
    while(!nodes.empty()) {
        for(int sz = nodes.size(); sz > 0; sz--) {
            cur = nodes.front();
            nodes.pop();
            cur->next = sz > 1 ? nodes.front() : nullptr;
            if(cur->left) {
                nodes.push(cur->left);
            }
            if(cur->right) {
                nodes.push(cur->right);
            }
        }
    }
    return root;
}

如果给定的二叉树是棵完美二叉树：116. Populating Next Right Pointers in Each Node

img 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 针对完美二叉树的递归式解法
Node* connect(Node* root) {
    if(!root) {
        return nullptr;
    }
    // 递归函数的定义就是将 p 和 q 两节点相连
    function<void(Node*, Node*)> helper = [&](Node* p, Node* q) {
        if(!p || !q) {
            return;
        }
        p->next = q;
        helper(p->left, p->right);
        helper(q->left, q->right);
        helper(p->right, q->left);
    };
    helper(root->left, root->right);
    return root;
}
98. Validate Binary Search Tree

给定二叉树的根，确定它是否是有效的二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isValidBST(TreeNode* root) {
    // 必须将对上层节点的约束传递给下层节点
    // 限定以 root 为根的子树节点必须满足 min->val < root.val < max->val
    function<bool(TreeNode*, TreeNode*, TreeNode*)> helper = [&](TreeNode* root, TreeNode* min, TreeNode* max) {
        if(!root) {
            return true;
        }
        if(min && root->val <= min->val) {
            return false;
        }
        if(max && root->val >= max->val) {
            return false;
        }
        // 这时 left 节点的最大就是 root, right 节点的最小值就是 root
        return helper(root->left, min, root) && helper(root->right, root, max);
    };
    return helper(root, nullptr, nullptr);
}
1373. Maximum Sum BST in Binary Tree

给定二叉树的根，找出所有是BST的子树，分别计算这些子树的所有节点值的和， 返回其中的最大值。

二叉搜索树的定义如下：

任意节点的左子树中的键值都小于此节点的键值。
任意节点的右子树中的键值都大于此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。

Example 1:

img 
1
2
3
Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Example 2:

img

1
2
3
Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 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
31
32
33
34
35
36
37
38
39
int maxSumBST(TreeNode* root) {
    int res = 0;
    // 递归函数返回值依次是
    // 1. 以 root 为根的 BST 子树节点值的总和, 如果其不是 BST, 此值为 0
    // 2. 以 root 为根的树中节点的最小值, 如果其不是 BST, 此值为 INT_MIN
    // 3. 以 root 为根的树中节点的最大值, 如果其不是 BST, 此值为 INT_MAX 
    auto postOrder = [&res](auto& postOrder, TreeNode* root) {
        if(!root) {
            return make_tuple(0, INT_MAX, INT_MIN);
        }
        auto [leftSum, leftMinVal, leftMaxVal] = postOrder(postOrder, root->left);
        auto [rightSum, rightMinVal, rightMaxVal] = postOrder(postOrder, root->right);
        // 如果当前节点的左子树中节点的最大值比当前节点还大
        // 或者当前节点的右子树中节点的最小值比当前节点还小
        // 以当前节点为根的子树就不是 BST
        // 因此总和为 0
        // 最小值为 INT_MIN 以致于右子树中包含此树的树也被认定为非 BST
        // 最大值为 INT_MAX 以致于左子树中包含此树的树也被认定为非 BST
        if(leftMaxVal >= root->val || rightMinVal <= root->val) {
            return make_tuple(0, INT_MIN, INT_MAX);
        }
        // 此时, 以当前节点为根的子树是 BST
        // 计算此树的总和并更新最大值
        int sum = leftSum + root->val + rightSum;
        res = max(res, sum);
        // 最后还要返回以当前节点为根的子树的信息
        // 其总和就为 sum
        // 1. 当前节点有可能是叶子节点或者只有一颗子树
            // 所以最小值为当前节点的值和左子树中最小的值相比取小者
            // 最大值为当前节点的值和右子树中最大的值相比取大者
            // 因为 if(!root) return {0, INT_MAX, INT_MIN}; 语句
            // 保证了左子树中最小的值为 INT_MAX, 右子树中最大的值为 INT_MIN
            // 所以比较的结果肯定是 root->val
        // 2. 当前节点有两棵子树, 那么比较的结果肯定不是 root->val (这是 BST 的规则!)
        return make_tuple(sum, min(root->val, leftMinVal), max(root->val, rightMaxVal));
    };
    postOrder(postOrder, root);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// make_tuple(isBST, sumOfBST, minVal, maxVal)
int maxSumBST(TreeNode* root) {
    int res = 0;
    auto post = [&](auto&& post, auto&& root) {
        if(root == nullptr) {
            // 空树也是 BST
            return make_tuple(true, 0, INT_MAX, INT_MIN);
        }
        auto&& [l_isBST, l_sumOfBST, l_minVal, l_maxVal] = post(post, root->left);
        auto&& [r_isBST, r_sumOfBST, r_minVal, r_maxVal] = post(post, root->right);
        if(!l_isBST || !r_isBST || root->val <= l_maxVal || root->val >= r_minVal) {
            // 不是 BST 的话, 其他值都无所谓了
            return make_tuple(false, 0, 0, 0);
        }
        int sum = l_sumOfBST + root->val + r_sumOfBST;
        res = max(res, sum);
        return make_tuple(true, sum, min(root->val, l_minVal), max(root->val, r_maxVal));
    };
    post(post, root);
    return res;
}
297. Serialize and Deserialize Binary Tree

序列化是将数据结构或对象转换为位序列的过程，以便可以将其存储在文件或内存缓冲区中，或者通过网络连接链接进行传输，以便稍后在相同或另一台计算机环境中进行重构。

设计一种用于对二叉树进行序列化和反序列化的算法。 序列化和反序列化算法的工作方式没有任何限制。 你只需要确保可以将二叉树序列化为字符串，并且可以将该字符串反序列化为原始树结构。

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
class Codec {
public:
    // 前序遍历解法
    string serialize(TreeNode* root) {
        string res;
        serialize(root, res);
        return res;
    }
    
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        return deserialize(ss);
    }
    
private:
    void serialize(TreeNode* root, string& res) {
        if(!root) {
            res += "# ";
            return;
        }
        res += to_string(root->val) + " ";
        serialize(root->left, res);
        serialize(root->right, res);
    }
    
    TreeNode* deserialize(stringstream& ss) {
        if(!ss) {
            return nullptr;
        }
        string temp;
        ss >> temp;
        if(temp == "#") {
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(temp));
        root->left = deserialize(ss);
        root->right = deserialize(ss);
        return 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
42
43
44
45
46
class Codec {
public:
    // 后序遍历解法
    string serialize(TreeNode* root) {
        string res;
        serialize(root, res);
        return res;
    }
    
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        vector<string> encoded;
        string s;
        while(getline(ss, s, ' ')) {
            encoded.push_back(s);
        }
        return deserialize(encoded);
    }
    
private:
    void serialize(TreeNode* root, string& res) {
        if(!root) {
            res += "# ";
            return;
        }
        serialize(root->left, res);
        serialize(root->right, res);
        res += to_string(root->val) + " ";
    }
    
    TreeNode* deserialize(vector<string>& encoded) {
        if(encoded.empty()) {
            return nullptr;
        }
        string s = encoded.back();
        encoded.pop_back();
        if(s == "#") {
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(s));
        // 后序遍历需要先构造右孩子, 再构造左孩子
        root->right = deserialize(encoded);
        root->left = deserialize(encoded);
        return 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
42
43
44
45
46
47
48
49
50
51
class Codec {
public:
    // 层序遍历解法
    string serialize(TreeNode* root) {
        string encoded;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            auto node = q.front();
            q.pop();
            if(node) {
                encoded += to_string(node->val) + " ";
                q.push(node->left);
                q.push(node->right);
            }
            else {
                encoded += "# ";
            }
        }
        return encoded;
    }
    
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        string nodeVal;
        ss >> nodeVal;
        if(nodeVal == "#") {
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(nodeVal));
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* root = q.front();
            q.pop();
            if(ss >> nodeVal) {
                if(nodeVal != "#") {
                    root->left = new TreeNode(stoi(nodeVal));
                    q.push(root->left);
                }
            }
            if(ss >> nodeVal) {
                if(nodeVal != "#") {
                    root->right = new TreeNode(stoi(nodeVal));
                    q.push(root->right);
                }
            }
        }
        return root;
    }
};
653. Two Sum IV - Input is a BST

给定一个二叉搜索树和一个目标数，如果BST中存在两个元素的总和等于给定的目标数，则返回true。

Example:

img 
1
2
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 方法 1 基本思想都是借助 BST 的中序遍历结果是升序排列的, 然后借助双指针搜索即可
// 方法 2 无论使用什么遍历 (递归或迭代), 都借助哈希表在遍历的过程中记录已经出现的值
bool findTarget(TreeNode* root, int k) {
    unordered_set<int> setting;
    auto helper = [&](auto&& helper, auto root) {
        if(!root) {
            return false;
        }
        if(setting.count(k - root->val)) {
            return true;
        }
        setting.insert(root->val);
        return helper(helper, root->left) || helper(helper, root->right);
    };
    return helper(helper, root);
}
114. Flatten Binary Tree to Linked List

给定二叉树的根，将树展平为“链表”：“链表”应使用相同的TreeNode类，其中右子指针指向列表中的下一个节点，而左子指针始终为null。

“链表”的顺序应与二叉树的前序遍历顺序相同。

img 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 递归思想: 相信递归函数的定义并毫不怀疑的去调用它!
// 此例中, void flatten(TreeNode* root) 函数的定义就是将 root 平展
// 只需要注意递归基的处理就可以了
void flatten(TreeNode* root) {
    if(root) {
        flatten(root->left);
        flatten(root->right);
        // 此时左右两棵子树都已经 flatten 完毕了
        TreeNode* temp = root->right; // 备份右子树
        root->right = nullptr;
        // 1. 将右孩子指针指向左子树, 随后左孩子指针置空
        if(root->left) {
            root->right = root->left;
            root->left = nullptr;
        }
        // 2. 沿着新右指针一直往前走, 定位到尾节点
        while(root && root->right) {
            root = root->right;
        }
        // 3. 将尾节点指向右子树
        root->right = temp;
    }
}
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
/*
	1
   / \
  2   5
 / \   \
3   4   6
// 将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6
// 将原来的右子树接到左子树的最右边节点
    1
     \
      2
     / \
    3   4
         \
          5
           \
            6
// 将 2 的左子树插入到右子树的地方
    1
     \
      2
       \
        3       4
                 \
                  5
                   \
                    6
// 将原来的右子树接到左子树的最右边节点
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6
*/
void flatten(TreeNode* root) {
    auto cur = root;
    while(cur) {
        if(cur->left) {
            auto pre = cur->left;
            while(pre->right) {
                pre = pre->right;
            }
            // 将原来的右子树接到左子树的最右边节点
            pre->right = cur->right;
            // 将左子树插入到右子树的地方
            cur->right = cur->left;
            cur->left = nullptr;
        }
        // 考虑下一个节点
        cur = cur->right;
    }
}
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

给定一个原始树和一个克隆树，克隆树是原始树的副本。并给出对原始树中某目标节点的引用。

返回对克隆树中相同节点的引用。

请注意，不允许您更改两个树或目标节点中的任何一个，并且答案必须是对克隆树中节点的引用。

注意：你的解答要适用于在树上允许有重复的值的情况。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 树上允许有重复的值意味着不能通过比较节点的值来返回目标节点
// 题目已经给出保证 original cloned target 都不为 null
// 直接对两棵树同步遍历
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
    if(!original) {
        return nullptr;
    }
    if(original == target) {
        return cloned;
    }
    // 先在左子树中找
    TreeNode* found = getTargetCopy(original->left, cloned->left, target);
    // 没找到再去右子树中找
    if(!found) {
        found = getTargetCopy(original->right, cloned->right, target);
    }
    return found;
}
99. Recover Binary Search Tree

给定一个二叉搜索树的根节点，恰好树中的两个节点错误地交换了。 在不更改其结构的前提下，恢复这棵二叉搜索树。

Example 1 Example 2
img img

Example 1:

1
2
3
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

1
2
3
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

注意：使用O(n)空间复杂度的解决方案非常简单。 你能设计一个O(1)空间解决方案吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 首先要知道, BST 的中序遍历是有序的
// 然后注意到, 如果树中有两个节点被交换了
// 在中序遍历序列中必然会出现逆序对 (可能一对, 也可能两对)
// 一对的情况是被交换的两个节点在中序遍历序列中相邻
// 此时我们有两个指针来分别定位这一逆序对的两个节点
// 交换它们的值即可
// 被交换的两个节点不相邻就会出现两对逆序对的情况
// 此时, 有一个指针定位前一个逆序对的第一个节点
// 另一个指针定位后一个逆序对的第二个节点
// 交换它们的值即可

// 从这题要学会如何跟踪遍历过程中当前节点的前一个节点的技术
void recoverTree(TreeNode* root) {
    // 定位逆序对的第一个节点
    TreeNode* first = nullptr;
    // 定位逆序对的第二个节点
    TreeNode* second = nullptr;
    // 始终指向当前访问节点的前一个节点
    TreeNode* pre = nullptr;
    auto inorder = [&](auto&& inorder, auto* cur) {
        if(cur == nullptr) {
            return;
        }
        inorder(inorder, cur->left);
        if(pre && pre->val > cur->val) {
            // 如果为空, 说明遇到的是第一个逆序对
            // 当前节点是逆序对的第二个节点
            // 第一个节点由 pre 指出, 更新 first
            // 如果不为空, 说明遇到的是第二个逆序对
            // 就不更新 first, 因为我们定位第二个逆序对的第一个节点没有用
            if(first == nullptr) {
                first = pre;
            }
            // 无论是第几个逆序对
            // second 都指向逆序对的第二个节点
            second = cur;
        }
        // 持续跟踪前一个节点
        pre = cur;
        inorder(inorder, cur->right);
    };
    inorder(inorder, root);
    swap(first->val, second->val);
}
687. Longest Univalue Path

给定二叉树的根，返回最长路径的长度，其中路径中的每个节点都具有相同的值。 此路径可能会也可能不会通过根。

两个节点之间的路径长度由它们之间的边数表示。

Example 1:

img 
1
2
Input: root = [1,4,5,4,4,5]
Output: 2

Example 2:

img 
1
2
Input: root = [5,4,5,1,1,5]
Output: 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
int longestUnivaluePath(TreeNode* root) {
    int maxPath = 0;
    // 该递归函数的定义就是返回以 root 为起点的符合条件的路径的最大长度
    auto post = [&](auto&& post, auto cur) -> int {
        if(cur == nullptr) {
            return 0;
        }
        int leftMax = post(post, cur->left);
        int rightMax = post(post, cur->right);
        int LeftMaxFromRoot = 0;
        int rightMaxFromRoot = 0;
        // 如果当前节点的值与其左孩子的值相等
    	// 那么它就可以和其左孩子的路径连在一块, 路径长度 +1
        if(cur->left && cur->left->val == cur->val) {
            LeftMaxFromRoot = leftMax + 1;
        }
        // 如果当前节点的值与其右孩子的值相等
    	// 那么它就可以和其右孩子的路径连在一块, 路径长度 +1
        if(cur->right && cur->right->val == cur->val) {
            rightMaxFromRoot = rightMax + 1;
        }
        // 注意这两条路径是不一样的
        maxPath = max(maxPath, LeftMaxFromRoot + rightMaxFromRoot);
        // 而以 root 为起点的符合条件的路径的最大长度为这两条路径的较大者
        return max(LeftMaxFromRoot, rightMaxFromRoot);
    };
    post(post, root);
    return maxPath;
}
654. Maximum Binary Tree

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

  1. 二叉树的根是数组中的最大元素。
  2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
  3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

Constraints:

  • All integers in nums are unique.

Example:

img 
1
2
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
{
    return construct(nums, 0, nums.size() - 1);
}

// 构造闭区间 [lo, hi] 内的元素
TreeNode* construct(vector<int>& nums, int lo, int hi)
{
    // base case
    if(lo > hi) return nullptr;
    // 找到最大值
    int maxIndex = findMax(nums, lo, hi);
    
    /* 另外, 装逼的话, 获取数组中最大元素的索引可以这样写
    int maxIndex = distance(nums.begin(),
    						max_element(nums.begin() + lo, nums.begin() + hi + 1));
    */
    
    // 以最大值为根节点
    TreeNode* root = new TreeNode(nums[maxIndex]);
    // 左子树为最大值左边的
    root->left = construct(nums, lo, maxIndex - 1);
    // 右子树为最大值右边的
    root->right = construct(nums, maxIndex + 1, hi);
    
    return root;
}

int findMax(vector<int>& nums, int lo, int hi)
{
    int maxVal = INT_MIN;
    int index;
    for(int i = lo; i <= hi; i++)
    {
        if(nums[i] > maxVal)
        {
            index = i;
            maxVal = nums[i];
        }
    }
    return index;
}
998. Maximum Binary Tree II

最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。

给出最大树的根节点root。

就像之前的654. Maximum Binary Tree问题那样，给定的树是从列表A递归地使用下述Construct(A)例程构造的：

如果A为空，返回null
否则，令A[i]作为A的最大元素。创建一个值为A[i]的根节点root
root的左子树将被构建为Construct([A[0], A[1], ..., A[i-1]])
root的右子树将被构建为Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
返回root
请注意，我们这里没有直接给定A，只有一个根节点root = Construct(A).

假设B是A的副本，并在末尾附加值val。题目数据保证B中的值是不同的。返回Construct(B)。

Example 1:
img img 
1
2
3
Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: A = [1,4,2,3], B = [1,4,2,3,5]

Example 2:
img img 
1
2
3
Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: A = [2,1,5,4], B = [2,1,5,4,3]

Example 3:
img img 
1
2
3
Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: A = [2,1,5,3], B = [2,1,5,3,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 先要明确一点, 最大二叉树指的是在构造的时候最大值左边的为左子树, 右边的为右子树
// 因为是放在数组右边的, 所以新节点必然在右子树中
TreeNode* insertIntoMaxTree(TreeNode* root, int val)
{
    // 如果比人家右子树中的所有节点都小
    // 只能作为叶子节点了
    if(!root) return new TreeNode(val);
    // 如果目标值当前节点的值大
    // 说明以当前节点为根的子树要成为我的左子树才行
    // 因为我是放在最右边的, 你在我左边我还比你大
    if(val > root->val)
        return new TreeNode(val, root, nullptr);
    // 否则, 就要向右边搜索位置
    // 因为你在原来最大值的右边
    root->right = insertIntoMaxTree(root->right, val);
    return root;
}
508. Most Frequent Subtree Sum

给定一棵树的根，要求你找到最频繁的子树总和。

节点的子树总和定义为由以该节点为根的子树（包括节点本身）形成的所有节点值的总和。 那么，最频繁的子树总和的值是多少？如果有平局，则以任意顺序返回具有最高频率的所有值。

Examples 1
Input:

1
2
3
   5
 / \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

1
2
3
   5
 / \
2   -5

return [2], since 2 happens twice, however -5 only occur once.

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
// 思想就是先通过递归获得所有子树的和
// 递归的过程中记录下来每一个确定的和出现的次数
// 这需要一个哈希表来记录 sum --> preq 的映射

// 但是问题来了, 之后我们要获取出现次数最多的, 也就是值(频率)最大的键
// 并且频率还有可能相同而出现重复
// 第一种方法是 auto maxFreqSum = *max_element(mapping.begin(), mapping.end(), cmp);
// 注意, cmp 需要定制 auto cmp = [](const pair<int, int>& a, const pair<int, int>& b)
//                 			{ return a.second < b.second; };
// 这种方法效率有点低, 有多少个重复的 freq, 我们就需要遍历哈希表多少次
// 最坏情况下，时间复杂度为 O(n2)

// 第二种方法是再使用一个 multimap 来 [逆映射] 原 unordered_map 中的键值对
// for(auto elem : mapping)
//        mappingSwap.insert({elem.second, elem.first});
// 需要注意的是, 使用有序可重复哈希表, 将原来的键变成值, 值变成键
// 然后通过逆迭代器直接获得最大键元素 (在红黑树的最右下边嘛)
// 最坏时间复杂度将为 O(n) 啦

// 第一种方法
// vector<int> findFrequentTreeSum(TreeNode* root)
// {
//     unordered_map<int, int> mapping;
//     subTreeSum(root, mapping);
//     auto cmp = [](const pair<int, int>& a, const pair<int, int>& b)
//                 { return a.second < b.second; };
//     vector<int> res;
//     int preFreq = 0;
//     while(1)
//     {
//         if(mapping.empty()) break;
//         auto maxFreqSum = *max_element(mapping.begin(), mapping.end(), cmp);
//         if(!res.empty() && maxFreqSum.second != preFreq)
//             break;
//         preFreq = maxFreqSum.second;
//         res.push_back(maxFreqSum.first);
//         mapping.erase(maxFreqSum.first);
//     }
//     return res;
// }

// 第二种方法
vector<int> findFrequentTreeSum(TreeNode* root)
{
    unordered_map<int, int> mapping;
    multimap<int, int> mappingSwap;
    subTreeSum(root, mapping);
    
    for(auto elem : mapping)
        mappingSwap.insert({elem.second, elem.first});
    
    vector<int> res;
    if(mappingSwap.empty()) return res;
    
    int preFreq = mappingSwap.rbegin()->first;
    for(auto it = mappingSwap.rbegin(); it != mappingSwap.rend(); it++)
    {
        if(it->first != preFreq) break;
        res.push_back(it->second);
    }
   
    return res;
}

int subTreeSum(TreeNode* root, unordered_map<int, int>& mapping)
{
    if(!root) return 0;
    int leftSum = subTreeSum(root->left, mapping);
    int rightSum = subTreeSum(root->right, mapping);
    
    int rootSum = leftSum + rightSum + root->val;
    mapping[rootSum]++;
    
    return rootSum;
}
236. Lowest Common Ancestor of a Binary Tree

给定一棵二叉树，找到树中两个给定节点的最低公共祖先（LCA）。一个节点的祖先可以是它自己。

Constraints:

  1. 所有Node.val互不相同
  2. p != q
  3. p 和 q均存在于给定的二叉树中。
img 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 接下来的几道题全是最低公共祖先的问题
// 这题的限制是给定的两个节点都存在树中
// 基本思想就是借助递归, 时刻牢记递归函数的定义, 并且毫不怀疑的使用它
// 这题中, lowestCommonAncestor 函数的定义就是, 接受一个根节点和两个在树中的其它节点
// 返回它们的 LCA
// 所以, 利用后序遍历, 先分别在当前节点的左右子树中找给定两个节点的 LCA
// 根据返回值判断寻找情况
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    // 如果当前节点为空, 肯定找不到 LCA 了
    if(!root) return nullptr;
    // left 为左子树中的寻找情况
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    // right 为右子树中的寻找情况
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    // 注意, 如果当前节点属于这两个节点之一
    // 意味着 当前节点就是它们的最低公共祖先啦
    if(root == p || root == q) return root;
    // 如果在左子树中和右子树中都找到了一个 LCA
    // 同样的, 说明当前节点就是它们的 LCA
    if(left && right) return root;
    // 否则, 返回在 以当前节点为根的子树 中给定节点的 LCA
    return left ? left : right;
}
1644. Lowest Common Ancestor of a Binary Tree II

给定一棵二叉树的根节点root，返回给定节点p和q的最近公共祖先（LCA）节点。如果p或q之一不存在于该二叉树中，返回null。

Constraints:

  1. 所有Node.val互不相同
  2. 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
27
28
29
30
31
32
33
34
35
36
37
38
// 这题和 I 题不同之处在于
// 给定的两个节点可能不在树中
// 所以, 这里我们使用两个 flag
// 在后序遍历的同时, 标志给定的两个节点是否在树中
// 其余的逻辑和 I 题一样
bool pIsInTree = false;
bool qIsInTree = false;

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    TreeNode* res = nullptr;
    // 辅助递归函数返回 LCA
    res = helper(root, p, q);
    // 如果有任何一个节点不在树中, 返回 null
    if(!pIsInTree || !qIsInTree) return nullptr;
    return res;
}

TreeNode* helper(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if(!root) return nullptr;
    
    TreeNode* left = helper(root->left, p, q);
    TreeNode* right = helper(root->right, p, q);
    // 将上题中的 if(root == p || root == q) return root; 分开写就行了
    if(root == p)
    {
        pIsInTree = true;
        return root;
    }
    if(root == q)
    {
       qIsInTree = true;
       return root;
    }
    if(left && right) return root;
    return left ? left : right;
}
1650. Lowest Common Ancestor of a Binary Tree III

给定一棵二叉树中的两个节点p和q，返回它们的最近公共祖先节点（LCA）。

每个节点都包含其父节点的引用（指针）。Node的定义如下：

1
2
3
4
5
6
7
struct Node
{
    int val;
    Node* left;
    Node* right;
    Node* parent;
}

Constraints:

  1. 所有Node.val互不相同
  2. p != q
  3. 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
27
// 这题中的树的节点都有指向父亲的指针, 而且还说给定的两个节点还肯定存在
// 那就更简单了, 直接分别从给定的两个节点逐层向上找
// 借助一个哈希集合, 第一个节点向上找的过程中, 经过的每一个父节点都放进一个集合内
// 等第二个节点向上找的时候, 如果遇到已经在哈希集合中的父节点 (首个遇到的)
// 那就说明这个节点就是它们的 LCA 啦
// 和查找链表的交叉点的思路一样
Node* lowestCommonAncestor(Node* p, Node* q)
{
    unordered_set<Node*> setting;
    // p 先向上, 同样的自己也可以是自己的祖先
    while(p)
    {
        // 所以自己也得放进集合
        setting.insert(p);
        p = p->parent;
    }

    while(q)
    {
        // 已经在集合中了, 就是它!
        if(setting.count(q)) return q;
        setting.insert(q);
        q = q->parent;
    }
    
    return nullptr;
}
1676. Lowest Common Ancestor of a Binary Tree IV

给定一棵二叉树的根节点root和TreeNode类对象的数组（列表）nodes，返回nodes中所有节点的最近公共祖先（LCA）。数组（列表）中所有节点都存在于该二叉树中，且二叉树中所有节点的值都是互不相同的。

Constraints:

  1. 所有的Node.val都是互不相同的。
  2. 所有的nodes[i]都存在于该树中。
  3. 所有的nodes[i]都是互不相同的。

img

示例 1:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
输出: 2
解释: 节点 4 和 7 的最近公共祖先是 2。

示例 2:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
输出: 5
解释: 节点 7、6、2 和 4 的最近公共祖先节点是 5。
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
// 这一题, 我笑了
// I 题是找两个节点的 LCA
// 这题找多个节点的, 思路完全一样
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes)
{
    // 先将 nodes 中的节点们都放进一个哈希集合中
    unordered_set<TreeNode*> setting;
    for(auto node : nodes)
        setting.insert(node);
    
    return dfs(root, setting);
}

TreeNode* dfs(TreeNode* root, unordered_set<TreeNode*>& setting)
{
    if(!root) return nullptr;
    
    TreeNode* left = dfs(root->left, setting);
    TreeNode* right = dfs(root->right, setting);
    // 将 I 题中的 if(root == p || root == q) return root; 换个写法就行了
    if(setting.count(root)) return root;
    
    if(left && right) return root;
    return left ? left : right;
}
235. Lowest Common Ancestor of a Binary Search Tree

给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if(p == root || q == root) return root;

    if(p->val < root->val && q->val < root->val)
        return lowestCommonAncestor(root->left, p, q);
    else if(p->val > root->val && q->val > root->val)
        return lowestCommonAncestor(root->right, p, q);

    return root;
}
101. Symmetric Tree

给定二叉树，请检查其是否是其自身的镜像（即围绕其中心对称）。

Example:

img 
1
2
Input: root = [1,2,2,3,4,4,3]
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isSymmetric(TreeNode* root)
{
    if(!root) return true;
    return helper(root->left, root->right);
}
// 左右子树同步遍历
bool helper(TreeNode* p, TreeNode* q)
{
    // 如果都为空, 显然对称
    if(!p && !q) return true;
    // 此时两者必有不为 null 的
    // 就判断是否有为 null 的
    if(!p || !q) return false;
    // 此时两者都不为 null
    // 就判断它们的值是否相等
    if(p->val != q->val) return false;

    return helper(p->left, q->right) && helper(p->right, q->left);
}
1372. Longest ZigZag Path in a Binary Tree

给你一棵以root为根的二叉树，二叉树中的交错路径定义如下：

选择二叉树中任意节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为0）。

请你返回给定树中最长交错路径的长度。

Example 1 Example 2
img img

Example 1:

1
2
3
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

1
2
3
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
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
// 递归形式 1
// 0 表示方向向左
// 1 表示方向向右
int res = 0;
int longestZigZag(TreeNode* root)
{
    helper(root->left, 0, 1);
    helper(root->right, 1, 1);
    return res;
}

void helper(TreeNode* node, bool dir, int depth)
{
    if(!node) return;
    
    res = max(res, depth);
    if(dir)
    {
        // 如果当前节点是从右方向过来的
        // 之后就要转去左方向
        helper(node->left, 0, depth + 1);
        // 同时还可以接着去右方向
        // 只不过深度要重新计算
        helper(node->right, 1, 1);
    }
    else
    {
        // 如果当前节点是从左方向过来的
        // 之后就要转去右方向
        helper(node->right, 1, depth + 1);
        // 同时还可以接着去左方向
        // 只不过深度要重新计算
        helper(node->left, 0, 1);
    }
}

// 递归形式 2
int res = 0;
int helper(TreeNode* root, bool dir)
{
    if(!root) return 0;

    int tmp_L = 1 + helper(root->left, 0);
    int tmp_R = 1 + helper(root->right, 1);

    res = max(res, tmp_L);
    res = max(res, tmp_R);

    return dir ? tmp_L : tmp_R;
}
int longestZigZag(TreeNode* root)
{
    helper(root, 0);
    // helper(root, 1);
    return res - 1;
}
173. Binary Search Tree Iterator

实现一个二叉搜索树迭代器类BSTIterator，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode* root)初始化BSTIterator类的一个对象。BST的根节点root会作为构造函数的一部分给出。指针应初始化为一个不存在于BST中的数字，且该数字小于BST中的任何元素。

bool hasNext()如果向指针右侧遍历存在数字，则返回true；否则返回false。
int next()将指针向右移动，然后返回指针处的数字。注意，指针初始化为一个不存在于BST中的数字，所以对next()的首次调用将返回BST中的最小元素。

你可以假设next()调用总是有效的，也就是说，当调用next()时，BST的中序遍历中至少存在一个下一个数字。

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
// 这题考察二叉树的中序遍历的迭代实现
// 只不过把循环分摊在每次调用 next 函数里
class BSTIterator
{
public:
    BSTIterator(TreeNode* root) : _pointer(root) {}
    // 这段和是中序遍历的迭代式写法 while(1) 循环体里的代码完全一样
    int next()
    {
        while(_pointer)
        {
            _stack.push(_pointer);
            _pointer = _pointer->left;
        }
        
        _pointer = _stack.top();
        int val = _pointer->val;
        _stack.pop();

        _pointer = _pointer->right;
        return val;
    }
    
    bool hasNext()
    {
        // 只有当 _pointer 为空并且 _stack 也为空的情况下
        // 才没有下一个节点
        return _pointer || !_stack.empty();
    }

private:
    TreeNode* _pointer;
    stack<TreeNode*> _stack;
};