二叉树算法精解：从基础遍历到高频面试题-平芜编程栈

1. 二叉树算法训练的核心价值

作为一名经历过多次算法面试的老兵，我深知二叉树在技术面试中的特殊地位。根据《代码随想录》的统计，二叉树相关题目在头部互联网企业的算法面试中出现频率高达65%，远高于其他数据结构。这也是为什么几乎所有优质算法训练营都会将二叉树作为重点突破章节。

在实际工程中，二叉树的应用场景同样广泛：从数据库索引的B+树实现，到游戏引擎中的场景图管理，再到机器学习中的决策树算法，二叉树的身影无处不在。掌握二叉树不仅是为了面试，更是构建高效、优雅代码的基础能力。

2. 二叉树基础概念精要

2.1 二叉树的核心特性

二叉树每个节点最多有两个子节点，这个看似简单的特性却衍生出丰富的算法变种。理解以下三个基础性质是解题的关键：

递归性质：每个子树本身也是二叉树，这使得递归成为处理二叉树最自然的思路
遍历顺序：前序、中序、后序遍历对应不同的处理时机
层级关系：广度优先遍历（层序遍历）揭示节点的横向关系

提示：建议在纸上手动绘制各种形态的二叉树（完全二叉树、满二叉树、普通二叉树），直观感受节点间的连接方式。

2.2 二叉树的代码表示

最常见的二叉树节点定义如下（以Python为例）：

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

这个简洁的结构却能表示任意复杂的二叉树形态。在实际解题时，我习惯为节点添加__str__方法方便调试：

def __str__(self): return f"Node({self.val})" if self else "None"

3. 二叉树遍历的六种姿势

3.1 深度优先遍历（DFS）

3.1.1 递归实现

递归写法最直观体现二叉树的结构特点：

# 前序遍历 def preorder(root): if not root: return print(root.val) # 处理当前节点 preorder(root.left) # 左子树 preorder(root.right) # 右子树

三种遍历方式的区别仅在于处理节点的时机：

前序：节点 → 左 → 右
中序：左 → 节点 → 右
后序：左 → 右 → 节点

3.1.2 迭代实现

面试常要求用迭代实现遍历，这里以前序遍历为例：

def preorder_iter(root): stack = [] while stack or root: while root: print(root.val) # 处理节点 stack.append(root) root = root.left root = stack.pop() root = root.right

技巧：迭代实现中序遍历只需调整打印时机，后序遍历则需要增加访问标记。

3.2 广度优先遍历（BFS）

层序遍历使用队列实现，能直观展示树的层级结构：

from collections import deque def level_order(root): if not root: return [] queue = deque([root]) while queue: node = queue.popleft() print(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right)

实际面试中，常要求分层输出结果（LeetCode 102题），这时需要记录层级信息：

def level_order_layers(root): if not root: return [] res = [] queue = deque([root]) while queue: layer = [] for _ in range(len(queue)): node = queue.popleft() layer.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(layer) return res

4. 高频面试题精解

4.1 二叉树的最大深度（LeetCode 104）

递归解法最简洁：

def max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right))

迭代解法可通过层序遍历计数：

def max_depth_bfs(root): if not root: return 0 depth = 0 queue = deque([root]) 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 depth

4.2 对称二叉树（LeetCode 101）

关键是比较左右子树的镜像关系：

def is_symmetric(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

4.3 路径总和（LeetCode 112）

典型回溯算法应用：

def has_path_sum(root, target): if not root: return False if not root.left and not root.right: return root.val == target return (has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val))

5. 二叉树构建技巧

5.1 根据遍历序列构建

已知中序+前序构建二叉树（LeetCode 105）：

def build_tree(preorder, inorder): if not preorder: return None root_val = preorder[0] root = TreeNode(root_val) idx = inorder.index(root_val) root.left = build_tree(preorder[1:idx+1], inorder[:idx]) root.right = build_tree(preorder[idx+1:], inorder[idx+1:]) return root

注意：这类题目需要明确各种遍历序列的特点，前序第一个元素是根节点，中序根节点左侧是左子树。

5.2 二叉搜索树验证（LeetCode 98）

利用中序遍历的有序性：

def is_valid_bst(root): stack = [] prev = float('-inf') while stack or root: while root: stack.append(root) root = root.left root = stack.pop() if root.val <= prev: return False prev = root.val root = root.right return True

6. 二叉树解题的通用思路

经过大量练习后，我总结出二叉树问题的解题框架：

确定遍历顺序：前序适合自上而下处理，后序适合自下而上汇总
选择递归/迭代：递归代码简洁但可能有栈溢出风险，迭代更可控
设计返回值：递归函数需要明确返回什么信息给上层
处理边界条件：空节点、单边子树等特殊情况
时空复杂度分析：通常递归是O(n)时间，O(h)空间（h为树高）

对于更复杂的问题（如最近公共祖先），可以组合多种遍历方式。例如LeetCode 236的解法：

def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right