二叉树算法实战：遍历与递归面试题精解-育师

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 res

3.2 自底向上层次遍历

只需将结果反转：

return res[::-1]

3.3 锯齿形层次遍历

通过标志位控制方向：

reverse = False if reverse: level = level[::-1] reverse = not reverse

4. 二叉树属性判断类题目

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 root

5.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)