24暑假算法刷题 | Day16 | LeetCode 513. 找树左下角的值，112. 路径总合，106. 从中序和后序遍历序列构造二叉树

---

513. 找树左下角的值

点此跳转题目链接

题目描述

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1
1
2

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
1
2

提示:

• 二叉树的节点个数的范围是 [1,104]
• -231 <= Node.val <= 231 - 1

题解

题目说的很清楚了，目标先是 “最底层” ，再是 “最左边” ，所以考虑先用层序遍历得到最底层的节点值数组，然后返回数组第一个值，即为“左下角”的值了：

vector<vector<int>> levelOrder(TreeNode *root)
{
    vector<vector<int>> res;
    queue<TreeNode *> q;
    if (!root)
        return res;
    q.push(root);
    while (!q.empty())
    {
        int size = q.size(); // 注意！先记录当前队长，因为之后会变
        vector<int> level;   // 当前这一层的节点值
        for (int i = 0; i < size; ++i)
        {
            level.push_back(q.front()->val);
            if (q.front()->left)
                q.push(q.front()->left);
            if (q.front()->right)
                q.push(q.front()->right);
            q.pop();
        }
        res.push_back(level);
    }
    return res;
}

int findBottomLeftValue(TreeNode *root)
{
    vector<vector<int>> levels = levelOrder(root); // 偷个懒，直接调用之前写过的层序遍历函数
    return levels[levels.size() - 1][0];
}
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 maxDepth = -1;
int leftBottonVal = 0;

void traversal(TreeNode *root, int depth)
{
    // 递归出口：叶子节点
    if (!root->left && !root->right && depth > maxDepth)
    {
        leftBottonVal = root->val; // 更新当前探索到的左下角值
        maxDepth = depth;          // 更新当前探索到的最大深度
        return;
    }
    // 先处理左孩子，这样保证同一层记录最左节点
    if (root->left)
        traversal(root->left, depth + 1);
    // 再处理右孩子
    if (root->right)
        traversal(root->right, depth + 1);
}

int findBottomLeftValue_II(TreeNode *root)
{
    traversal(root, 0);
    return leftBottonVal;
}
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

---

112. 路径总合

点此跳转题目链接

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
1
2
3

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
1
2
3
4
5
6

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
1
2
3

提示：

• 树中节点的数目在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

题解

首先可以用DFS递归秒杀：

bool hasPathSum(TreeNode *root, int targetSum)
{
    // 递归出口1：空节点
    if (!root)
        return false;
    // 递归出口2：加上当前节点值求和等于targetSum，且当前节点为叶子节点
    if (root->val == targetSum && !root->left && !root->right)
        return true;
    // 递归探索左右子树
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}
1
2
3
4
5
6
7
8
9
10
11

然后再想想迭代法，发现这题和 257. 二叉树的所有路径 其实如出一辙（具体思路和注意细节见那篇题解），只需要将其中记录路径的逻辑替换成计算路径节点值之和就行了：

bool hasPathSum_II(TreeNode *root, int targetSum) {
    // 基于前序遍历的统一迭代法实现
    if (!root)
        return false;
    stack<TreeNode*> nodeSt;
    nodeSt.push(root);
    stack<int> sumSt;
    sumSt.push(root->val);
    while (!nodeSt.empty()) {
        TreeNode *node = nodeSt.top();
        nodeSt.pop();
        int sum = sumSt.top(); 
        sumSt.pop();
        if (node) {
            if (node->right) {
                nodeSt.push(node->right); // 右
                sumSt.push(sum + node->right->val);
            }
            if (node->left) {
                nodeSt.push(node->left); // 左
                sumSt.push(sum + node->left->val);
            }
            nodeSt.push(node); // 中
            nodeSt.push(nullptr); // 空指针标记
            sumSt.push(sum);
        }
        else {
            if (sum == targetSum && !nodeSt.top()->left && !nodeSt.top()->right)
                return true;
            nodeSt.pop();
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

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

点此跳转题目链接

题目描述

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

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
1
2

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]
1
2

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

题解

蛮锻炼思维的一道题目