二叉树核心算法实战

1. 二叉树基础与遍历方法

二叉树是每个节点最多有两个子节点的树结构，在算法面试和工程实践中极为常见。理解它的基本性质是解决所有二叉树问题的前提。二叉树的节点通常定义为包含值、左子节点和右子节点的结构体，用代码表示如下：

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

二叉树的遍历方式主要有四种，每种都有其特定的应用场景：

1. 前序遍历：根节点 → 左子树 → 右子树。适合需要先处理根节点信息的场景，比如树的序列化。
2. 中序遍历：左子树 → 根节点 → 右子树。对二叉搜索树会得到有序序列。
3. 后序遍历：左子树 → 右子树 → 根节点。适合先处理子节点再处理父节点的场景，如计算子树属性。
4. 层序遍历：按层级从上到下、从左到右遍历。适合需要按层级分析的场景。

递归实现前序遍历的代码示例：

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

在实际工程中，递归虽然简洁但可能存在栈溢出风险。这时可以用迭代法替代，例如用栈实现前序遍历：

def preorder_iterative(root): stack = [root] while stack: node = stack.pop() if node: print(node.val) stack.append(node.right) # 右子节点先入栈 stack.append(node.left) # 左子节点后入栈

2. 判断相同树与子树匹配

2.1 判断两棵树是否相同

这个问题看似简单，却是很多复杂问题的基础。核心思路是同步遍历两棵树，比较每个节点的结构和值。递归解法的时间复杂度是O(n)，空间复杂度取决于树的高度。

def isSameTree(p, q): if not p and not q: # 都为空 return True if not p or not q: # 一个为空一个不为空 return False if p.val != q.val: # 值不相等 return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

这个解法有几个关键点需要注意：

1. 终止条件要处理所有可能的空节点情况
2. 先判断结构再判断值
3. 递归调用要同时比较左右子树

2.2 子树匹配问题

子树匹配可以复用相同树的判断逻辑。基本思路是对主树的每个节点都作为根节点，判断是否与目标子树相同。最坏情况下时间复杂度是O(mn)，其中m和n分别是两棵树的节点数。

优化版的解法：

def isSubtree(root, subRoot): if not subRoot: return True if not root: return False if isSameTree(root, subRoot): return True return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

实际工程中，如果树很大，可以考虑序列化后使用字符串匹配算法，如KMP，将时间复杂度优化到O(m+n)。

3. 二叉树深度相关问题

3.1 计算最大深度

最大深度是指从根节点到最远叶子节点的最长路径上的节点数。递归解法非常直观：

def maxDepth(root): if not root: return 0 left_depth = maxDepth(root.left) right_depth = maxDepth(root.right) return max(left_depth, right_depth) + 1

迭代法可以使用层序遍历，记录遍历的层数：

def maxDepth_iterative(root): if not root: return 0 queue = [root] depth = 0 while queue: depth += 1 level_size = len(queue) for _ in range(level_size): node = queue.pop(0) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth

3.2 判断平衡二叉树

平衡二叉树是指每个节点的左右子树高度差不超过1。直接按照定义实现的解法时间复杂度是O(n²)，因为对每个节点都要计算子树高度：

def isBalanced(root): if not root: return True left_height = maxDepth(root.left) right_height = maxDepth(root.right) return abs(left_height - right_height) <= 1 and \ isBalanced(root.left) and \ isBalanced(root.right)

更高效的O(n)解法是在计算高度的同时判断平衡性：

def isBalanced(root): def check(node): if not node: return 0 left = check(node.left) right = check(node.right) if left == -1 or right == -1 or abs(left - right) > 1: return -1 return max(left, right) + 1 return check(root) != -1

4. 对称二叉树与进阶问题

4.1 判断对称二叉树

对称二叉树是指左右子树互为镜像。解决思路是比较左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点。

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

迭代法可以使用队列实现：

def isSymmetric_iterative(root): if not root: return True queue = [(root.left, root.right)] while queue: left, right = queue.pop(0) if not left and not right: continue if not left or not right: return False if left.val != right.val: return False queue.append((left.left, right.right)) queue.append((left.right, right.left)) return True

4.2 二叉树路径问题

二叉树路径问题是面试中的高频考点。比如求从根节点到叶子节点的所有路径：

def binaryTreePaths(root): def dfs(node, path, res): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append("->".join(path)) dfs(node.left, path, res) dfs(node.right, path, res) path.pop() res = [] dfs(root, [], res) return res

路径问题通常需要结合回溯思想，在递归调用前后维护当前路径状态。