代码随想录-Day18

513. 找树左下角的值

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

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

方法一：深度优先搜索

class Solution {
    int curVal = 0;
    int curHeight = 0;

    public int findBottomLeftValue(TreeNode root) {
        int curHeight = 0;
        dfs(root, 0);
        return curVal;
    }

    public void dfs(TreeNode root, int height) {
        if (root == null) {
            return;
        }
        height++;
        dfs(root.left, height);
        dfs(root.right, height);
        if (height > curHeight) {
            curHeight = height;
            curVal = root.val;
        }
    }
}

这段代码是用来解决一个问题：在一棵二叉树中找到最底层最左边的节点的值。代码采用了深度优先搜索（DFS）的方式遍历二叉树，并利用两个类变量curVal和curHeight记录当前遍历到的最深的节点值以及相应的深度。

• class Solution 是定义的解题类。

• int curVal = 0; 和 int curHeight = 0; 是类变量，分别用来存储当前已知的最深节点的值和其所在深度。

• public int findBottomLeftValue(TreeNode root) 是主方法，输入为二叉树的根节点 root，输出是最底层最左边节点的值。这里定义了一个局部变量 curHeight 来记录当前遍历的深度，虽然它与类变量同名，但在方法作用域内互不影响。首先调用 dfs 方法对树进行深度优先遍历，并传入根节点和初始高度0。遍历完成后，返回类变量 curVal 作为结果。

• public void dfs(TreeNode root, int height) 是一个私有的辅助方法，用于递归地进行深度优先遍历。输入参数为当前节点 root 和该节点的当前高度 height。

  • 如果节点为空，则直接返回，结束本次递归。
  • 然后将高度加1，准备遍历下一层。
  • 先递归遍历左子树，再递归遍历右子树，这样的顺序保证了在遍历到同一深度的节点时，先访问左边的节点。
  • 在递归调用返回之后，检查当前节点的高度是否大于已知的最大深度 curHeight。如果是，则更新 curHeight 和 curVal，使得它们分别记录当前遍历到的最深深度及该深度最左边节点的值。

通过这样的DFS遍历，能够确保最后得到的 curVal 是位于最底层最左边的节点的值。

方法二：广度优先搜索

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ret = 0;
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            if (p.right != null) {
                queue.offer(p.right);
            }
            if (p.left != null) {
                queue.offer(p.left);
            }
            ret = p.val;
        }
        return ret;
    }
}

这段代码实现了在二叉树中找到最底层最左边的节点值。代码使用了广度优先搜索（BFS）进行层次遍历。以下是代码的详细解释：

方法签名

public int findBottomLeftValue(TreeNode root)

该方法接受一个 TreeNode 类型的根节点 root 作为输入，返回一个整数类型的最底层最左边的节点值。

变量声明

int ret = 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();

• ret 变量用于存储最终的最底层最左边的节点值。
• queue 是一个队列，用于执行广度优先搜索。初始化为 ArrayDeque 类型。

初始化队列

queue.offer(root);

将根节点 root 放入队列中。

广度优先搜索

while (!queue.isEmpty()) {
    TreeNode p = queue.poll();
    if (p.right != null) {
        queue.offer(p.right);
    }
    if (p.left != null) {
        queue.offer(p.left);
    }
    ret = p.val;
}

• 使用 while 循环，当队列不为空时继续循环。
• TreeNode p = queue.poll(); 取出队列的第一个节点 p。
• 如果 p 的右子节点不为空，将其放入队列。
• 如果 p 的左子节点不为空，将其放入队列。
• 每次循环，将当前节点的值 p.val 赋值给 ret。

返回结果

return ret;

返回 ret 作为最底层最左边的节点值。

代码逻辑

1. 初始化：将根节点放入队列中。
2. 广度优先搜索：
   • 每次从队列中取出一个节点。
   • 优先将右子节点入队，再将左子节点入队。
   • 更新 ret 为当前节点的值。
3. 终止条件：当队列为空时，循环结束。此时，ret 存储的就是最底层最左边的节点值。

思路解释

使用广度优先搜索遍历树的每一层，并且每次都优先处理右子节点。这意味着当到达最底层时，最先被处理的节点将是最左边的节点。每次更新 ret，最终 ret 会是最底层最左边的节点值。

示例

考虑如下二叉树：

        2
       / \
      1   3
     / \
    4   5
   /
  7

• 初始时，队列为 [2]
• 取出 2，加入 3 和 1，队列为 [3, 1]
• 取出 3，队列为 [1]
• 取出 1，加入 5 和 4，队列为 [5, 4]
• 取出 5，队列为 [4]
• 取出 4，加入 7，队列为 [7]
• 取出 7，队列为空

最终返回 7，即最底层最左边的节点值。

112. 路径总和

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

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

方法一：广度优先搜索

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }
}

这段代码实现了一个名为 Solution 的类，其中有一个方法 hasPathSum，用于判断一棵二叉树中是否存在从根节点到叶子节点的路径，使得沿途经过的节点值之和等于给定的 sum 值。该方法采用了广度优先搜索（BFS）的策略，使用两个队列分别存储待遍历的节点和对应节点值的累加和。

• 方法签名：public boolean hasPathSum(TreeNode root, int sum)，接收二叉树的根节点 root 和目标和 sum，返回值是一个布尔值，表示是否存在满足条件的路径。

• 初始化两个队列：Queue<TreeNode> queNode 用于存储待遍历的节点，Queue<Integer> queVal 用于存储从根节点到当前节点路径上节点值的累加和。首先将根节点和其值入队。

• 使用 while 循环处理队列，直到队列为空，表示树已被完全遍历。

  • 每次循环从队列中弹出一个节点 now 和对应的累加和 temp。
  • 判断当前节点是否为叶子节点（即左右子节点均为 null），若是且累加和 temp 等于目标和 sum，则返回 true，表示找到了满足条件的路径。
  • 若当前节点不是叶子节点，将其左右子节点（若存在）及其对应的累加和（子节点值加 temp）分别入队，以便下一轮循环继续遍历。

• 如果循环结束还没有找到满足条件的路径，则返回 false。

需要注意的是，这段代码的逻辑是正确的，但是它解决的问题是“是否存在从根节点到叶子节点的路径，其节点值之和等于给定的 sum”，而不是原问题描述中寻找二叉树中最底层最左边的节点值。对于后者，应该采用不同的逻辑来追踪每一层的第一个节点。

方法二：递归

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

这段代码是使用递归方法实现的 Java 程序，用于解决“判断一棵二叉树中是否存在从根节点到叶子节点的路径，使得沿途经过的节点值之和等于给定的 sum”的问题。这里是针对原始问题的正确解答，与之前讨论的寻找最底层最左边节点值的问题无关。下面是代码的详细解释：

• 类 Solution 中定义了方法 hasPathSum，它接收两个参数：一个 TreeNode 类型的参数 root 表示二叉树的根节点，一个整型参数 sum 表示目标和。

• 首先，检查根节点是否为空，如果为空则直接返回 false，表示不存在这样的路径。

• 然后，检查当前节点是否为叶子节点（即没有左右子节点）。如果是叶子节点，并且该节点的值等于 sum，则返回 true，表示找到了一条满足条件的路径。

• 如果当前节点不是叶子节点，递归地在左子树和右子树中寻找满足条件的路径。这里通过减去当前节点的值 root.val 来更新目标和 sum，分别对左子树和右子树调用 hasPathSum 方法。如果左子树或右子树中任意一侧存在满足条件的路径，就返回 true；如果两侧都没有满足条件的路径，则返回 false。

通过这种方式，代码高效地遍历了整棵树，仅沿着有可能达到目标和的路径进行探索，最终确定是否存在满足条件的路径。这是一种典型的深度优先搜索（DFS）策略。

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

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

方法一：递归

class Solution {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

    public TreeNode helper(int in_left, int in_right) {
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return null;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map.get(root_val);

        // 下标减一
        post_idx--;
        // 构造右子树
        root.right = helper(index + 1, in_right);
        // 构造左子树
        root.left = helper(in_left, index - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        // 从后序遍历的最后一个元素开始
        post_idx = postorder.length - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (Integer val : inorder) {
            idx_map.put(val, idx++);
        }
        
        return helper(0, inorder.length - 1);
    }
}

这段代码是用于根据给定的中序遍历（inorder）和后序遍历（postorder）数组重建一棵二叉树。代码定义了一个名为 Solution 的类，其中有两个成员变量和两个主要方法：

1. 成员变量：

   • post_idx：记录当前处理的后序遍历数组中的元素位置。
   • postorder 和 inorder：分别存储给定的后序遍历和中序遍历数组。
   • idx_map：一个哈希映射，存储中序遍历中每个元素对应的索引，便于快速查找。

2. 主要方法：

   • helper(int in_left, int in_right)：这是一个递归方法，用于根据给定的中序遍历区间 [in_left, in_right] 重建子树。方法内部首先判断区间有效性，然后根据后序遍历数组的当前元素（即子树根节点）分割中序遍历区间，递归地构建右子树和左子树，最后返回根节点。

   • buildTree(int[] inorder, int[] postorder)：这是主要的接口方法，接收中序遍历和后序遍历的数组，初始化必要的数据，包括设置 post_idx 初始值、构建哈希映射 idx_map，然后调用 helper 方法从整个中序遍历区间开始重建二叉树，并返回根节点。

整体逻辑遵循二叉树后序遍历的特性，即后序遍历的最后一个元素是树的根节点，利用中序遍历来确定左右子树的划分。通过哈希表快速定位根节点在中序遍历中的位置，以此分治递归地构建整颗二叉树。

方法二：迭代

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = inorder.length - 1;
        for (int i = postorder.length - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.right = new TreeNode(postorderVal);
                stack.push(node.right);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(postorderVal);
                stack.push(node.left);
            }
        }
        return root;
    }
}

这段代码实现了一个名为 Solution 的类，其中包含一个方法 buildTree，该方法接收两个整型数组参数 inorder 和 postorder，分别表示某个二叉树的中序遍历和后序遍历结果。目的是根据这两个遍历结果重建出原来的二叉树结构，并返回该二叉树的根节点。

代码逻辑分析如下：

1. 首先检查 postorder 数组是否为空或者长度为0，如果是，则直接返回 null，表示没有树可构建。
2. 初始化根节点：根据后序遍历特点，最后一个元素是树的根节点，所以创建一个新的 TreeNode，其值为 postorder 数组的最后一个元素。
3. 准备一个 Deque（双端队列）stack，并把根节点压入栈中。
4. 初始化 inorderIndex 为 inorder 数组的最后一个有效索引，因为在后序遍历中根节点之后的元素将构成右子树或左子树。
5. 从 postorder 数组的倒数第二个元素开始遍历（索引 i 从 postorder.length - 2 到 0）：
   • 获取当前遍历到的后序遍历值 postorderVal。
   • 检查栈顶元素（即当前正在构建的子树的根节点）的值是否与 inorder[inorderIndex] 匹配：
     • 如果不匹配，说明当前 postorderVal 应该属于栈顶节点的右子树，因此创建一个新的右子节点，将其值设为 postorderVal，并压入栈中。
     • 如果匹配，说明已经处理完栈顶节点的右子树，需要向上回溯到可以连接新节点（当前 postorderVal 对应节点）作为左子节点的位置。通过一个 while 循环不断弹出栈顶节点并更新 inorderIndex，直到找到合适的位置（或栈为空）。
       • 找到合适位置后，为当前 node 创建左子节点，值为 postorderVal，并将其压入栈中，继续处理下一个 postorder 中的元素。
6. 遍历完成后，栈中构建的结构即为完整的二叉树，返回根节点。

这种方法利用了后序遍历（左右根）和中序遍历（左根右）的特点，通过栈来辅助构建二叉树，从后序遍历数组反向构建，有效地恢复了原二叉树的结构。