1. 二叉树刷题进阶指南作为一名在算法领域摸爬滚打多年的老手我深知二叉树是面试中最常考察的数据结构之一。今天要分享的是我在刷完力扣前50道二叉树简单题后针对其中最具教学意义的12道题目编号20-32的系统性总结。这些题目看似基础但蕴含着递归、迭代、层次遍历等多种解题范式是构建算法思维的绝佳材料。特别提示建议先掌握二叉树的前中后序递归写法这是理解本文所有解法的基础门槛。如果对递归还感到吃力可以参考我的《递归破局四步法》系列文章。2. 核心题目分类解析2.1 遍历类问题精讲104. 二叉树的最大深度堪称二叉树领域的Hello World。这道题的递归解法优雅得令人惊叹def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))但很多新手会忽略迭代解法实际上用层序遍历统计层数更为直观from collections import deque def maxDepth(root): if not root: return 0 queue deque([root]) depth 0 while queue: depth 1 for _ in range(len(queue)): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth112. 路径总和则展示了递归的另一种经典用法。关键点在于递归终止条件要处理空节点目标值要随着递归递减只在叶子节点判断是否满足条件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)2.2 结构判断类问题101. 对称二叉树是检验递归思维的试金石。很多同学第一次尝试时会陷入单棵树递归的思维定式实际上需要比较两棵树def isSymmetric(root): def compare(left, right): if not left and not right: return True if not left or not right: return False return left.val right.val and \ compare(left.left, right.right) and \ compare(left.right, right.left) return compare(root.left, root.right) if root else True迭代解法使用队列实现同样逻辑from collections import deque def isSymmetric(root): if not root: return True queue deque([(root.left, root.right)]) while queue: left, right queue.popleft() if not left and not right: continue if not left or not right or left.val ! right.val: return False queue.append((left.left, right.right)) queue.append((left.right, right.left)) return True2.3 搜索类问题实战700. 二叉搜索树中的搜索展示了BST的特性应用。递归解法直接利用BST的有序性def searchBST(root, val): if not root or root.val val: return root return searchBST(root.left, val) if val root.val else \ searchBST(root.right, val)但更推荐迭代写法空间效率更高def searchBST(root, val): while root and root.val ! val: root root.left if val root.val else root.right return root3. 高频考点深度剖析3.1 递归的四种经典模式通过分析这组题目我总结出二叉树递归的四种基本模式自顶向下处理先处理当前节点再递归子节点前序遍历自底向上聚合先递归子节点再处理当前节点后序遍历对称比较同时递归处理两个关联节点如对称二叉树路径累积在递归过程中维护状态变量如路径总和以226. 翻转二叉树为例展示不同递归模式的应用# 自顶向下写法 def invertTree(root): if not root: return None root.left, root.right root.right, root.left # 先处理当前节点 invertTree(root.left) invertTree(root.right) return root # 自底向上写法 def invertTree(root): if not root: return None left invertTree(root.left) right invertTree(root.right) root.left, root.right right, left # 后处理当前节点 return root3.2 迭代解法的统一模板对于不喜欢递归或者担心栈溢出的情况掌握迭代写法至关重要。我提炼出一个通用的二叉树迭代模板from collections import deque def iterative_template(root): if not root: return ... queue deque([root]) result [] while queue: level_size len(queue) for _ in range(level_size): node queue.popleft() # 处理当前节点 ... # 添加子节点 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return ...这个模板稍加修改就能解决107. 二叉树的层序遍历 II等问题。关键在于最后对结果列表的反转def levelOrderBottom(root): if not root: return [] queue deque([root]) result [] while queue: level [] for _ in range(len(queue)): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result[::-1]4. 避坑指南与优化技巧4.1 递归常见陷阱终止条件不全忘记处理空节点导致无限递归变量污染在递归中直接修改传入参数重复计算没有利用备忘录优化重复子问题返回值混淆不清楚递归函数应该返回什么以110. 平衡二叉树为例展示如何避免重复计算def isBalanced(root): def height(node): if not node: return 0 left height(node.left) right height(node.right) if left -1 or right -1 or abs(left - right) 1: return -1 return max(left, right) 1 return height(root) ! -1这个解法通过返回-1表示不平衡同时计算高度避免了单独计算高度和平衡性的双重递归。4.2 空间复杂度优化对于617. 合并二叉树这样的问题直接在原树上修改可以节省空间def mergeTrees(root1, root2): if not root1: return root2 if not root2: return root1 root1.val root2.val root1.left mergeTrees(root1.left, root2.left) root1.right mergeTrees(root1.right, root2.right) return root1如果要求不能修改原树则需要创建新节点此时空间复杂度会从O(1)变为O(n)。5. 同类题目扩展训练为了帮助大家举一反三我整理了与这组题目相关的进阶练习题层次遍历变种103. 二叉树的锯齿形层序遍历路径问题升级113. 路径总和 II需要记录路径BST特性应用653. 两数之和 IV - 输入BST构造二叉树108. 将有序数组转换为二叉搜索树以108题为例展示如何利用BST特性递归构建平衡BSTdef sortedArrayToBST(nums): def helper(left, right): if left right: return None mid (left right) // 2 root TreeNode(nums[mid]) root.left helper(left, mid - 1) root.right helper(mid 1, right) return root return helper(0, len(nums) - 1)这个解法每次取中间元素作为根节点保证左右子树节点数平衡从而构建出高度平衡的BST。