1. 二叉树算法实战：Leetcode高频题精讲

作为一名刷过300+道Leetcode的老手，我深刻理解二叉树类题目在面试中的重要性。今天要分享的两道题（513.找树左下角的值、112.路径总和）都是二叉树章节的经典题型，在各大厂面试中出现频率极高。这两题看似简单，但其中蕴含的DFS/BFS应用技巧和边界条件处理，正是区分普通候选人和优秀工程师的关键。

2. 513.找树左下角的值深度解析

2.1 问题本质与解法选择

题目要求找出二叉树最后一行最左边的值。这个描述包含两个关键信息：

1. 最后一行 → 需要知道当前遍历的深度
2. 最左边 → 需要记录每行的第一个访问节点

这提示我们需要使用层序遍历（BFS）或者带深度记录的DFS。两种方法各有优劣：

• BFS天然按层遍历，可以直观获取每层第一个节点
• DFS代码更简洁，但需要维护最大深度和结果值

2.2 BFS标准解法实现

from collections import deque def findBottomLeftValue(root): queue = deque([root]) result = 0 while queue: level_size = len(queue) for i in range(level_size): node = queue.popleft() if i == 0: # 每层第一个节点 result = node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result

关键点：在每层循环开始时，队列中保存的就是当前层的所有节点。通过记录level_size，我们可以精确控制每层的遍历范围。

2.3 DFS优化解法

def findBottomLeftValue(root): max_depth = -1 result = 0 def dfs(node, depth): nonlocal max_depth, result if not node: return if depth > max_depth: max_depth = depth result = node.val dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 0) return result

注意：DFS解法中必须先递归左子树！这是为了保证当深度相同时，左侧节点会被优先记录。

2.4 复杂度分析与对比

3. 112.路径总和全方位剖析

3.1 问题变形与常见误区

题目要求判断是否存在从根到叶子的路径，使得路径和等于给定值。需要注意：

1. 路径必须到叶子节点结束（不能中途停止）
2. 节点值可能为负数（不能提前剪枝）

常见错误解法：

# 错误示例：未检查叶子节点 def hasPathSum(root, target): if not root: return target == 0 # 错误！ return hasPathSum(root.left, target - root.val) or hasPathSum(root.right, target - root.val)

3.2 标准递归解法

def hasPathSum(root, target): if not root: return False if not root.left and not root.right: # 叶子节点检查 return target == root.val return hasPathSum(root.left, target - root.val) or hasPathSum(root.right, target - root.val)

3.3 迭代解法与栈的应用

def hasPathSum(root, target): if not root: return False stack = [(root, root.val)] while stack: node, curr_sum = stack.pop() if not node.left and not node.right and curr_sum == target: return True if node.right: stack.append((node.right, curr_sum + node.right.val)) if node.left: stack.append((node.left, curr_sum + node.left.val)) return False

技巧：使用栈模拟DFS时，注意压入顺序（右子树先入栈，保证左子树先处理）

3.4 路径总和变种题

1. 113.路径总和II：返回所有满足条件的路径
2. 437.路径总和III：不限定从根到叶子的路径
3. 124.二叉树中的最大路径和：路径可以不经过根节点

4. 二叉树遍历的底层原理

4.1 递归的系统栈实现

递归解法本质是利用了系统调用栈。以路径总和为例：

hasPathSum(A, 22) ├─ hasPathSum(B, 17) │ ├─ hasPathSum(D, 11) │ │ ├─ hasPathSum(None, 6) → False │ │ └─ hasPathSum(None, 6) → False │ └─ hasPathSum(E, 17) │ ├─ hasPathSum(None, 13) → False │ └─ hasPathSum(None, 13) → False └─ hasPathSum(C, 17) ├─ hasPathSum(F, 16) │ ├─ hasPathSum(None, 15) → False │ └─ hasPathSum(None, 15) → False └─ hasPathSum(G, 16) ├─ hasPathSum(None, 15) → False └─ hasPathSum(None, 15) → False

4.2 前序、中序、后序的选择策略

不同遍历顺序在解题中的应用：

• 前序：适合从上到下的累积计算（如路径总和）
• 后序：适合从下到上的信息收集（如树的高度）
• 中序：BST相关题目（如验证BST）

5. 高频错误与调试技巧

5.1 空指针异常预防

二叉树题最常见的运行时错误：

# 错误示例 if root.val == target: # 可能访问None的val属性

正确做法：

if not root: return False # 或其他适当处理 if root.val == target: ...

5.2 测试用例设计模板

有效的测试用例应包含：

1. 空树
2. 单节点树
3. 完全二叉树
4. 倾斜树（全部左子树或右子树）
5. 包含负值的树

示例测试用例：

class TestSolution(unittest.TestCase): def test_path_sum(self): # 5 # / \ # 4 8 # / / \ # 11 13 4 # / \ \ # 7 2 1 root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(8) # ... 继续构建树 self.assertTrue(hasPathSum(root, 22)) self.assertFalse(hasPathSum(root, 100)) self.assertTrue(hasPathSum(TreeNode(1), 1)) # 单节点 self.assertFalse(hasPathSum(None, 0)) # 空树

5.3 可视化调试技巧

在纸上画出递归调用树：

1. 标记每个节点的当前target值
2. 用不同颜色标注递归路径
3. 特别关注叶子节点的判断条件

对于层序遍历问题，可以打印每层的节点值：

while queue: print([node.val for node in queue]) # 打印当前层 ...

6. 面试实战建议

6.1 解题步骤标准化

1. 明确问题：复述题目要求，确认边界条件
2. 举例说明：用具体例子演示输入输出
3. 选择算法：解释为什么选择DFS/BFS
4. 编写代码：边写边讲思路
5. 测试验证：用设计的测试用例验证

6.2 复杂度分析话术模板

"这个算法的时间复杂度是O(n)，因为我们需要访问每个节点一次。空间复杂度方面，最坏情况下是O(n)（当树退化为链表时），平均情况下是O(logn)对应树的深度。"

6.3 常见follow-up问题

1. 如果节点值范围很大怎么办？（考虑数值溢出）
2. 如何优化空间复杂度？（迭代代替递归）
3. 如果树经常变化但频繁查询路径和？（前缀和+哈希表）

7. 扩展练习与资源推荐

7.1 推荐刷题路径

1. 基础遍历：144.前序, 94.中序, 145.后序
2. 层序遍历：102.二叉树的层序遍历, 107.层序遍历II
3. 路径问题：257.二叉树的所有路径, 129.求根到叶子节点数字和
4. 构造问题：105.从前序与中序构造二叉树, 106.从中序与后序构造二叉树

7.2 可视化工具推荐

1. Leetcode Playground：内置树可视化功能
2. Visualgo.net：交互式算法学习平台
3. Binary Tree Visualizer：专用于二叉树的可视化工具

7.3 进阶学习资料

1. 《算法导论》红黑树章节
2. MIT OpenCourseWare 6.006 算法课
3. Leetcode官方二叉树专题卡片

在实际面试中，我发现很多候选人能够写出基本解法，但往往忽略了边界条件检查（如空树、单节点树）。建议在写完代码后，立即用这些边界案例测试，这能展现你的代码严谨性。另外，对于路径总和这类问题，递归解法虽然简洁，但在面试官要求解释复杂度时，要能清晰说明递归栈的空间消耗与树高的关系。