Leetcode二叉树遍历实战：513与112题精解

1. 二叉树遍历实战Leetcode经典题目精解今天我们来深入探讨Leetcode上两道经典的二叉树题目——513.找树左下角的值和112.路径总和1。这两道题看似简单但包含了二叉树遍历的核心思想是面试中的高频考点。作为刷过300题的过来人我发现很多同学在这类题目上容易陷入思维定式今天我就分享一些实战经验和优化技巧。2. 题目513找树左下角的值2.1 问题重述与理解给定一个二叉树的根节点root找出该二叉树最底层最左边的节点值。注意不是左子树而是整个树在最后一层最靠左的节点。举个例子1 / \ 2 3 / / \ 4 5 6 / 7这个树的最底层最左边节点是7。2.2 解题思路分析这道题有两个关键点需要把握如何确定最底层如何确定最左边的节点我尝试过三种主流解法BFS层序遍历推荐DFS递归遍历DFS迭代遍历2.3 BFS层序遍历实现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注意这里使用双端队列deque比list效率更高popleft()是O(1)操作2.4 DFS递归解法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 result2.5 复杂度分析与选择时间复杂度两种方法都是O(N)N为节点数空间复杂度BFS最坏情况O(N)完全二叉树最后一层DFS最坏O(H)H为树高实际面试中我推荐BFS解法因为更符合直觉容易解释不需要递归栈避免栈溢出风险代码结构清晰容易写对3. 题目112路径总和13.1 问题描述给定一个二叉树和一个目标和判断该树中是否存在根节点到叶子节点的路径使得路径上所有节点值相加等于目标和。示例5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1目标和22返回true因为路径5→4→11→2的和为22。3.2 解题思路这道题的关键点是必须是根到叶子的完整路径路径和要严格等于目标值常见误区把中间节点当作叶子节点忽略了负数节点的情况3.3 递归解法递归是最直观的解法从根节点开始每次用目标和减去当前节点值直到叶子节点检查剩余和是否为0。def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: # 叶子节点 return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or \ hasPathSum(root.right, targetSum - root.val)3.4 迭代解法使用栈实现DFS同时记录到当前节点的累计和。def hasPathSum(root, targetSum): 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 targetSum: 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 False3.5 注意事项空树情况要单独处理必须走到叶子节点才算有效路径节点值可能为负数所以不能做提前剪枝递归解法可能栈溢出树很深时这时应该用迭代4. 二叉树遍历的通用技巧4.1 遍历方式选择BFS适合层相关操作如本题513DFS适合路径相关操作如本题112前中后序根据访问顺序需求选择4.2 常见优化手段双端队列加速BFS记忆化递归减少重复计算提前终止条件优化迭代代替递归避免栈溢出4.3 调试技巧打印树结构辅助理解def printTree(root, level0): if root: printTree(root.right, level 1) print( * 4 * level -, root.val) printTree(root.left, level 1)使用可视化工具如Leetcode的树可视化构造边界测试用例空树单节点树左/右斜树包含负数的树5. 同类题目推荐刷完这两题后可以继续挑战这些相似题目路径总和II输出所有路径路径总和III任意路径求根到叶子节点数字之和二叉树的右视图在每个树行中找最大值6. 面试实战建议根据我参加过的20场面试经验二叉树题目常考以下几点能否正确选择遍历方式边界条件处理是否全面代码是否简洁高效能否分析时间/空间复杂度建议在面试中先确认输入范围节点数、值范围举例说明思路边写代码边解释写完主动检查边界条件二叉树题目看似基础但要做到bug-free并不容易。我建议至少手写20道二叉树题目直到能10分钟内无错误写出中等难度题目为止。这两道题作为二叉树的基础题掌握后对理解更复杂的树形DP等问题有很大帮助。