1. 二叉树算法题解系列从遍历到递归的实战精讲最近在整理算法笔记时发现二叉树相关的题目总是高频出现在技术面试中。特别是LeetCode上编号144、145、94、102、226、101、104、111、222这九道经典题目涵盖了前中后序遍历、层次遍历、镜像对称、深度计算、节点统计等核心考点。今天我就用工程化的思维带大家系统性地吃透这些题目分享我在刷题过程中总结的解题模板和避坑指南。2. 基础遍历三连前序/中序/后序2.1 递归解法模板这三类遍历的递归写法是最容易理解的# 前序遍历144题 def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) # 中序遍历94题 def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) # 后序遍历145题 def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val]关键记忆点前序-中左右中序-左中右后序-左右中。递归写法虽然简洁但面试时往往要求用迭代实现。2.2 迭代解法精讲迭代写法需要显式使用栈来模拟递归过程。以前序遍历为例def preorderTraversal(root): stack, res [root], [] while stack: node stack.pop() if node: res.append(node.val) stack.append(node.right) # 先右后左 stack.append(node.left) return res中序遍历的迭代写法较为特殊需要指针辅助def inorderTraversal(root): stack, res [], [] curr root while curr or stack: while curr: # 左子树入栈 stack.append(curr) curr curr.left curr stack.pop() res.append(curr.val) curr curr.right return res避坑提示后序遍历的迭代写法最复杂建议先掌握前两种再挑战。可以尝试逆前序反转的思路。3. 层次遍历与变形题目3.1 标准层次遍历102题BFS队列是标准解法def levelOrder(root): from collections import deque queue, res deque([root]), [] while queue: level [] for _ in range(len(queue)): node queue.popleft() if node: level.append(node.val) queue.append(node.left) queue.append(node.right) if level: res.append(level) return res3.2 自底向上层次遍历只需将结果反转return res[::-1]3.3 锯齿形层次遍历通过标志位控制方向reverse False if reverse: level level[::-1] reverse not reverse4. 二叉树属性判断类题目4.1 对称二叉树101题递归判断镜像def isSymmetric(root): def check(l, r): if not l and not r: return True if not l or not r: return False return l.val r.val and check(l.left, r.right) and check(l.right, r.left) return check(root.left, root.right)4.2 二叉树的最大深度104题递归解法最直观def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))4.3 二叉树的最小深度111题注意与最大深度的区别def minDepth(root): if not root: return 0 if not root.left: return 1 minDepth(root.right) if not root.right: return 1 minDepth(root.left) return 1 min(minDepth(root.left), minDepth(root.right))常见误区直接套用最大深度模板会导致错误。最小深度必须到叶子节点左右子节点都为空5. 进阶题目解析5.1 翻转二叉树226题著名的Homebrew作者面试题def invertTree(root): if root: root.left, root.right invertTree(root.right), invertTree(root.left) return root5.2 完全二叉树的节点个数222题利用完全二叉树性质优化def countNodes(root): if not root: return 0 left_height right_height 0 l r root while l: left_height 1 l l.left while r: right_height 1 r r.right if left_height right_height: # 满二叉树 return 2**left_height - 1 return 1 countNodes(root.left) countNodes(root.right)性能分析时间复杂度优化到O(logN * logN)优于普通二叉树的O(N)解法6. 实战经验与优化技巧递归转迭代的通用方法所有递归算法都可以用栈循环改写但要注意前序/后序适合用显式栈层次遍历适合用队列中序遍历需要额外指针空间复杂度优化Morris遍历可以实现O(1)空间复杂度但会修改树结构调试技巧打印树结构使用层次遍历可视化小规模测试先验证3个节点的简单情况边界检查空树、单节点、左斜树等特殊情况常见面试陷阱问清楚输入是否为None确认节点值是否可能为负数是否需要处理重复值情况模板化训练建议每天练习一种遍历写法对比记忆不同解法的差异手写代码时注意缩进和括号匹配在实际面试中二叉树题目往往作为基础考察点。我建议至少完整刷过三遍这些经典题目第一遍理解思路第二遍优化代码第三遍限时白板编程。记住面试官最看重的是解题过程的沟通能力而不仅仅是最终答案的正确性。