二叉树算法精讲：遍历、构建与高频面试题

二叉树是数据结构中的核心内容，也是面试中的高频考点。本文系统讲解二叉树的遍历方法、构建技巧，以及常见算法问题的解决思路。

一、二叉树基础与遍历

1.1 二叉树的基本结构

二叉树是每个节点最多有两个子树的树结构，具有递归定义的特性。

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

1.2 深度优先遍历（DFS）

前序遍历：根 → 左 → 右

def preorder_traversal(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result

# 迭代解法
def preorder_iterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result
​

中序遍历：左 → 根 → 右

def inorder_traversal(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

# 迭代解法
def inorder_iterative(root):
    stack, result = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result
​

后序遍历：左 → 右 → 根

def postorder_traversal(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)
    dfs(root)
    return result

# 迭代解法（双栈法）
def postorder_iterative(root):
    if not root:
        return []
    stack1, stack2, result = [root], [], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        result.append(stack2.pop().val)
    return result
​

1.3 广度优先遍历（BFS）

层序遍历：逐层从左到右访问节点

from collections import deque

def level_order(root):
    if not root:
        return []
    queue, result = deque([root]), []
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    return result
​

二、二叉树构建与序列化

2.1 根据遍历序列构建二叉树

从前序和中序序列构建二叉树：

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

从中序和后序序列构建二叉树：

def build_tree_inorder_postorder(inorder, postorder):
    if not inorder or not postorder:
        return None
    
    root_val = postorder[-1]
    root = TreeNode(root_val)
    root_pos = inorder.index(root_val)
    
    root.left = build_tree_inorder_postorder(inorder[:root_pos], postorder[:root_pos])
    root.right = build_tree_inorder_postorder(inorder[root_pos+1:], postorder[root_pos:-1])
    
    return root
​

2.2 二叉树的序列化与反序列化

前序序列化：

def serialize(root):
    result = []
    def dfs(node):
        if not node:
            result.append("None")
            return
        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ",".join(result)

def deserialize(data):
    values = data.split(",")
    def dfs():
        if values[0] == "None":
            values.pop(0)
            return None
        root = TreeNode(int(values[0]))
        values.pop(0)
        root.left = dfs()
        root.right = dfs()
        return root
    return dfs()
​

三、经典二叉树算法

3.1 二叉树的最大深度

递归解法：

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

# 迭代解法（BFS）
def max_depth_iterative(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        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 depth
​

3.2 判断平衡二叉树

平衡二叉树：每个节点的左右子树深度差不超过1。

def is_balanced(root):
    def check_balance(node):
        if not node:
            return 0, True
        
        left_height, left_balanced = check_balance(node.left)
        right_height, right_balanced = check_balance(node.right)
        
        current_height = max(left_height, right_height) + 1
        is_balanced = (left_balanced and right_balanced and 
                      abs(left_height - right_height) <= 1)
        
        return current_height, is_balanced
    
    _, balanced = check_balance(root)
    return balanced
​

3.3 最近公共祖先

题目：给定一个二叉树，找到该树中两个指定节点p、q的最近公共祖先。

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
​

3.4 路径总和

题目：判断二叉树中是否存在根节点到叶子节点的路径，使得路径上所有节点值之和等于目标和。

def has_path_sum(root, target_sum):
    if not root:
        return False
    
    # 叶子节点
    if not root.left and not root.right:
        return root.val == target_sum
    
    remaining_sum = target_sum - root.val
    return (has_path_sum(root.left, remaining_sum) or 
            has_path_sum(root.right, remaining_sum))

# 找出所有路径
def path_sum(root, target_sum):
    result = []
    def dfs(node, current_path, current_sum):
        if not node:
            return
        
        current_path.append(node.val)
        current_sum += node.val
        
        # 如果是叶子节点且和等于目标
        if not node.left and not node.right and current_sum == target_sum:
            result.append(list(current_path))
        
        dfs(node.left, current_path, current_sum)
        dfs(node.right, current_path, current_sum)
        
        current_path.pop()  # 回溯
    
    dfs(root, [], 0)
    return result
​

四、进阶算法技巧

4.1 二叉搜索树的验证

二叉搜索树特性：左子树所有节点值 < 根节点值 < 右子树所有节点值

def is_valid_bst(root):
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (validate(node.left, min_val, node.val) and 
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))
​

4.2 二叉搜索树的第k大节点

def kth_largest(root, k):
    result = []
    def reverse_inorder(node):
        if not node or len(result) >= k:
            return
        reverse_inorder(node.right)  # 先右后左，降序
        result.append(node.val)
        reverse_inorder(node.left)
    
    reverse_inorder(root)
    return result[k-1] if k <= len(result) else None
​

4.3 二叉树的直径

直径：二叉树中任意两个节点路径长度中的最大值

def diameter_of_binary_tree(root):
    max_diameter = [0]  # 使用列表以便在闭包中修改
    
    def depth(node):
        if not node:
            return 0
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        
        # 更新直径
        max_diameter[0] = max(max_diameter[0], left_depth + right_depth)
        
        return max(left_depth, right_depth) + 1
    
    depth(root)
    return max_diameter[0]
​

4.4 二叉树的最大路径和

def max_path_sum(root):
    max_sum = [float('-inf')]
    
    def max_gain(node):
        if not node:
            return 0
        
        # 递归计算左右子树的最大贡献
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        
        # 当前节点的最大路径和
        current_sum = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], current_sum)
        
        # 返回节点的最大贡献
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum[0]
​

五、优化技巧与最佳实践

5.1 递归优化技巧

1. 尾递归优化：虽然Python不支持尾递归优化，但理解尾递归有助于写出更高效的代码
2. 剪枝优化：在搜索过程中提前终止不可能的分支
3. 记忆化：缓存重复计算的结果

# 剪枝示例：在二叉搜索树中快速查找
def search_bst(root, val):
    if not root or root.val == val:
        return root
    return search_bst(root.left, val) if val < root.val else search_bst(root.right, val)
​

5.2 迭代替代递归

递归可能导致栈溢出，在处理深度较大的树时使用迭代更安全。

# 前序遍历的迭代实现（莫里斯遍历）
def morris_preorder(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # 找到前驱节点
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result
​

六、总结与建议

掌握二叉树算法的关键要点：

1. 递归思维：理解递归的本质，能够将复杂问题分解为子问题
2. 画图分析：通过图形化理解问题，特别是路径问题
3. 模板记忆：掌握常见问题的解题模板，如DFS、BFS等
4. 边界处理：注意空树、单节点等特殊情况
5. 优化考虑：根据题目要求选择合适的算法和优化策略

二叉树是数据结构中的核心内容，建议从基础的遍历开始，逐步掌握构建、搜索、路径等复杂问题。通过大量练习，培养递归思维和问题分析能力。