day16 代码随想录算法训练营 二叉树专题4

1 今日打卡题

找树左下角的值 513. 找树左下角的值 – 力扣（LeetCode）

路径总和 112. 路径总和 – 力扣（LeetCode）

从中序遍历和后序遍历构造二叉树 106. 从中序与后序遍历序列构造二叉树 – 力扣（LeetCode）

2 找树左下角的值

2.1 迭代法

2.1.1 思路

使用队列实现层序遍历，逐层访问二叉树的节点； 遍历每一层时，先记录当前层第一个节点的值（即该层最左节点）； 按 “先左后右” 的顺序将下一层节点加入队列，确保每一层的第一个节点都是最左节点； 遍历完所有层后，最后一次记录的 “层最左节点值” 就是整棵树左下角的值（最后一层最左）。

2.1.2 实现代码

class Solution {
public int findBottomLeftValue(TreeNode root) {
// 1. 初始化队列，用于层序遍历（BFS），队列存储当前层的节点
Queue<TreeNode> que = new LinkedList<>();
// 根节点入队，启动遍历
que.offer(root);
// 存储每一层最左节点的值，最终返回最后一层的该值
int leftNum = 0;

// 2. 循环遍历每一层，直到队列为空（所有层遍历完）
while(!que.isEmpty()) {
// 获取当前层的节点数量（关键：区分不同层的节点）
int size = que.size();
// 记录当前层第一个节点的值（即该层最左节点值）
leftNum = que.peek().val;

// 3. 遍历当前层的所有节点
for(int i = 0; i < size; i++) {
// 取出当前层的一个节点
TreeNode cur = que.poll();
// 左子节点入队（先左后右，保证下一层最左节点先入队）
if(cur.left != null) que.offer(cur.left);
// 右子节点入队
if(cur.right != null) que.offer(cur.right);
}
}

// 4. 最后一次更新的leftNum就是最后一层最左节点的值，返回
return leftNum;
}
}

2.2 递归法

2.2.1 思路

变量设计：用两个成员变量分别记录最大深度（maxDepth）和结果值（res），避免递归传参的复杂度； 终止条件：遇到叶子节点时，判断其深度是否超过当前记录的最大深度 —— 若超过，说明找到了 “更深层的叶子节点”，更新最大深度和结果值； 遍历顺序：优先递归左子树，再递归右子树，保证同一深度下左叶子节点先被访问，不会被同深度的右叶子覆盖； 隐藏回溯：递归时传递 depth + 1（临时值），而非修改原 depth，递归返回后外层 depth 自动恢复，实现隐式回溯。

2.2.2 实现代码

class Solution {
// 成员变量：存储最终结果（最后一层最左叶子节点的值）
private int res;
// 成员变量：记录遍历到的最大深度（初始为-1，确保根节点深度0能触发更新）
private int maxDepth = -1;

// 主方法：入口，返回树左下角的值
public int findBottomLeftValue(TreeNode root) {
// 从根节点开始递归遍历，根节点初始深度为0
traversal(root, 0);
// 遍历完成后，res即为最后一层最左叶子节点的值
return res;
}

// 递归遍历函数：深度优先搜索（DFS）
// root：当前遍历的节点；depth：当前节点的深度
private void traversal(TreeNode root, int depth) {
// 递归终止条件：遇到叶子节点（无左右子节点）
if (root.left == null && root.right == null) {
// 关键判断：当前叶子节点深度 > 已记录的最大深度
// 说明找到了「更深层」的叶子节点，是目前最接近“最后一层”的节点
if (depth > maxDepth) {
maxDepth = depth; // 更新最大深度
res = root.val; // 更新结果为当前叶子节点值（左优先保证是左节点）
}
return; // 叶子节点无后续遍历，直接返回
}

// 优先遍历左子树（核心！保证同一深度下左叶子先被访问）
if (root.left != null) {
// 递归左子树，深度+1（传递临时值，隐含回溯，不修改外层depth）
traversal(root.left, depth + 1);
}

// 再遍历右子树
if (root.right != null) {
// 递归右子树，深度+1（传递临时值，隐含回溯）
traversal(root.right, depth + 1);
}
}
}

3 路径总和

3.1 思路

变量设计：用布尔成员变量 find 标记是否找到符合条件的路径，避免递归返回值的复杂处理； 递归逻辑： 累加当前节点值到路径和 sum 中； 遇到叶子节点时，判断路径和是否等于目标和，是则标记 find = true； 隐式回溯：利用 Java 基本类型值传递特性，递归传递累加后的 sum，递归返回后外层 sum 不变，无需手动回溯； 剪枝优化：一旦找到符合条件的路径（find = true），立即终止所有后续递归，避免无效遍历。

3.2 实现代码

class Solution {
// 标记是否找到符合条件的路径（根到叶子的和等于targetSum）
private boolean find = false;

// 主方法：入口，判断是否存在目标路径和
public boolean hasPathSum(TreeNode root, int targetSum) {
// 边界条件：空树直接返回false（无路径）
if (root == null) {
return false;
}
// 从根节点开始递归遍历，初始路径和为0
traversal(root, 0, targetSum);
// 返回是否找到目标路径
return find;
}

// 递归遍历函数：深度优先搜索（DFS）
// root：当前遍历的节点；sum：当前路径的累加和；targetSum：目标和
private void traversal(TreeNode root, int sum, int targetSum) {
// 剪枝：已找到目标路径，直接返回，无需继续遍历
if (find) {
return;
}

// 累加当前节点值到路径和中
sum += root.val;

// 递归终止条件：遇到叶子节点（无左右子节点）
if (root.left == null && root.right == null) {
// 判断当前路径和是否等于目标和，是则标记find为true
if (sum == targetSum) {
find = true;
}
return; // 叶子节点无后续节点，直接返回
}

// 优先遍历左子树（顺序不影响结果，仅遍历逻辑）
if (root.left != null) {
// 传递累加后的sum（值传递，递归内部修改不影响外层，天然回溯）
traversal(root.left, sum, targetSum);
}

// 遍历右子树
if (root.right != null) {
traversal(root.right, sum, targetSum);
}
}
}

4 从中序遍历和后序遍历构造二叉树

4.1 思路

特性利用： 后序遍历顺序：左子树 → 右子树 → 根节点（后序数组最后一个元素是整棵树的根）； 中序遍历顺序：左子树 → 根节点 → 右子树（可通过根节点位置划分左右子树）； 全局指针：用 post_idx 从后序数组末尾向前遍历（post_idx–），每次取当前未处理的最后一个元素作为子树的根； 哈希缓存：用 HashMap 缓存中序数组「值 – 索引」映射，避免每次查找根节点位置的 O (n) 开销； 递归构建： 先通过后序指针取根节点，再在中序数组中找到根节点位置，划分左右子树区间； 优先构建右子树，再构建左子树（适配 post_idx 从后往前的遍历顺序）； 递归终止条件：中序区间无元素（inLeft > inRight）。  

递归构建顺序：必须先右后左 原因：后序数组是「左→右→根」，post_idx 从后往前取元素，先取到的是「根→右子树根→右子树节点→左子树根」，只有先构建右子树，才能保证指针移动和节点匹配； 错误后果：若先左后右，会导致右子树的节点被错误分配给左子树，构建出的树结构完全错误。 全局指针 post_idx 的必要性 Java 基本类型是值传递，若将 post_idx 作为参数传递，递归内部的修改无法同步到外层，会导致指针位置错乱； 仅需初始化一次，递归中通过 post_idx– 持续向前移动，无需额外维护后序数组的区间边界。 哈希表的作用 提前缓存中序数组的值 – 索引，将查找根节点位置的时间复杂度从 O (n) 降到 O (1)，整体时间复杂度优化为 O (n)。 中序区间的边界（闭区间） 递归参数 inLeft/inRight 是闭区间 [inLeft, inRight]，终止条件 inLeft > inRight 表示当前区间无元素，返回 null。

4.2 实现代码

class Solution {
// 哈希表：缓存中序遍历数组的「值-索引」映射，快速查找根节点位置
private HashMap<Integer, Integer> map = new HashMap<>();
// 后序数组的遍历指针：从后序数组末尾向前移动，记录当前待处理的根节点位置
private int post_idx;

/**
* 主方法：入口，从中序+后序数组构建二叉树
* @param inorder 中序遍历数组
* @param postorder 后序遍历数组
* @return 构建后的二叉树根节点
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 1. 初始化哈希表：存储中序值对应的索引，O(n)时间
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// 2. 初始化后序指针：指向后序数组最后一个元素（整棵树的根节点）
post_idx = postorder.length – 1;
// 3. 递归构建二叉树，中序区间初始为[0, 后序数组长度-1]（闭区间）
TreeNode root = treeHelper(inorder, postorder, 0, postorder.length – 1);
return root;
}

/**
* 递归辅助函数：构建当前区间的子树
* @param inorder 中序遍历数组
* @param postorder 后序遍历数组
* @param inLeft 当前子树在中序数组中的左边界（闭）
* @param inRight 当前子树在中序数组中的右边界（闭）
* @return 当前子树的根节点
*/
private TreeNode treeHelper(int[] inorder, int[] postorder, int inLeft, int inRight) {
// 递归终止条件：中序区间无元素，返回空节点
if (inLeft > inRight) {
return null;
}

// 1. 取当前后序指针指向的元素作为子树根节点（后序最后一个元素是根）
int rootVal = postorder[post_idx–];
TreeNode root = new TreeNode(rootVal);

// 2. 查找根节点在中序数组中的索引，划分左右子树区间
int index = map.get(rootVal);

// 3. 关键：先构建右子树，再构建左子树（适配post_idx从后往前移动的逻辑）
// 右子树的中序区间：[index+1, inRight]
root.right = treeHelper(inorder, postorder, index + 1, inRight);
// 左子树的中序区间：[inLeft, index-1]
root.left = treeHelper(inorder, postorder, inLeft, index – 1);

// 返回当前构建好的子树根节点
return root;
}
}

5 额外题目

5.1 路径总和Ⅱ 113. 路径总和 II – 力扣（LeetCode）

5.1.1 思路

变量设计： path：记录当前递归路径上的节点值（临时路径）； res：存储所有符合条件的完整路径（最终结果）； 递归逻辑： 累加当前节点值到路径和 sum，并将节点值加入 path； 遇到叶子节点时，判断路径和是否等于目标和：若相等，将当前 path 的副本加入结果集； 递归遍历左、右子树，遍历完成后显式回溯（移除 path 最后一个元素），恢复路径状态； 终止条件：遇到叶子节点时完成当前路径的判断，直接返回。

5.1.2 实现代码

class Solution {
// 存储当前递归路径的节点值（临时路径，用于回溯）
private List<Integer> path = new ArrayList<>();
// 存储所有符合条件的完整路径（最终结果）
private List<List<Integer>> res = new ArrayList<>();

// 主方法：入口，返回所有根到叶子且和为targetSum的路径
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
// 边界条件：空树直接返回空结果
if (root == null) return res;
// 从根节点开始递归遍历，初始路径和为0
traversal(root, targetSum, 0);
return res;
}

// 递归遍历函数：DFS + 回溯
// root：当前遍历的节点；targetSum：目标和；sum：当前路径的累加和
public void traversal(TreeNode root, int targetSum, int sum) {
// 1. 累加当前节点值到路径和
sum += root.val;
// 2. 将当前节点值加入临时路径
path.add(root.val);

// 3. 递归终止条件：遇到叶子节点（无左右子节点）
if (root.left == null && root.right == null) {
// 判断当前路径和是否等于目标和
if (sum == targetSum) {
// 关键：添加path的副本到结果集（避免后续回溯修改结果）
res.add(new ArrayList<>(path));
}
// 叶子节点无后续遍历，直接返回（注意：此处不回溯，回溯在递归调用后执行）
return;
}

// 4. 递归遍历左子树
if (root.left != null) {
traversal(root.left, targetSum, sum);
// 关键：回溯——移除路径最后一个元素，恢复路径状态
path.remove(path.size() – 1);
}

// 5. 递归遍历右子树
if (root.right != null) {
traversal(root.right, targetSum, sum);
// 关键：回溯——移除路径最后一个元素，恢复路径状态
path.remove(path.size() – 1);
}
}
}

5.2 从前序遍历和后序遍历构造二叉树

5.2.1 思路

找根节点： 前序遍历顺序：根 → 左 → 右 → 前序数组第一个元素是根； 划分子树：利用中序遍历「左 → 根 → 右」的特性，通过根节点位置将中序数组划分为「左子树区间」和「右子树区间」； 递归构建：递归处理左、右子树区间，直到区间无元素（递归终止）； 哈希优化：用 HashMap 缓存中序数组「值 – 索引」，将查找根节点位置的时间复杂度从 O (n) 降到 O (1)。

前序数组头部（preIdx 从 0 往后移）、先左后右（符合前序「根→左→右」）

5.2.2 实现代码

class Solution {
// 前序数组遍历指针：从0开始向后移动（适配前序「根→左→右」）
private int preIdx;
// 缓存中序值-索引，快速找根节点位置
private HashMap<Integer, Integer> map = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
// 初始化中序值-索引映射
for(int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// 前序指针初始化为0（指向第一个元素，整棵树的根）
preIdx = 0;
// 递归构建，中序区间初始为[0, 长度-1]（闭区间）
TreeNode root = treeHelper(preorder, inorder, 0, inorder.length – 1);
return root;
}

private TreeNode treeHelper(int[] preorder, int[] inorder, int inLeft, int inRight) {
// 递归终止：中序区间无元素，返回空
if(inLeft > inRight) return null;
// 取当前前序指针指向的元素作为根（前序头是根），指针后移
int rootVal = preorder[preIdx++];
TreeNode root = new TreeNode(rootVal);
// 找根在中序的位置，划分左右子树
int index = map.get(rootVal);
// 关键：先构建左子树，再构建右子树（符合前序遍历顺序）
root.left = treeHelper(preorder, inorder, inLeft, index – 1);
root.right = treeHelper(preorder, inorder, index + 1, inRight);
return root;
}
}