Home

主题

二叉树 ​

基础结构 ​

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

# 构建二叉树
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6

root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3, None, TreeNode(6))

前序遍历（Preorder） ​

顺序：根 -> 左 -> 右

递归版本 ​

python
def preorder_recursive(root):
    if not root:
        return []
    return [root.val] + preorder_recursive(root.left) + preorder_recursive(root.right)

迭代版本（栈） ​

python
def preorder_iterative(root):
    """
    前序遍历：根 -> 左 -> 右
    使用栈模拟递归
    """
    if not root:
        return []
    
    result = []
    stack = [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

# 测试
print(preorder_iterative(root))  # [1, 2, 4, 5, 3, 6]

中序遍历（Inorder） ​

顺序：左 -> 根 -> 右

递归版本 ​

python
def inorder_recursive(root):
    if not root:
        return []
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

迭代版本 ​

python
def inorder_iterative(root):
    """
    中序遍历：左 -> 根 -> 右
    一直往左走，访问节点时转向右子树
    """
    result = []
    stack = []
    curr = root
    
    while curr or stack:
        # 一直往左走
        while curr:
            stack.append(curr)
            curr = curr.left
        
        # 弹出一个节点
        curr = stack.pop()
        result.append(curr.val)
        
        # 转向右子树
        curr = curr.right
    
    return result

# 测试：对于 BST，中序遍历得到有序序列
print(inorder_iterative(root))  # [4, 2, 5, 1, 3, 6]

后序遍历（Postorder） ​

顺序：左 -> 右 -> 根

递归版本 ​

python
def postorder_recursive(root):
    if not root:
        return []
    return postorder_recursive(root.left) + postorder_recursive(root.right) + [root.val]

迭代版本 ​

python
def postorder_iterative(root):
    """
    后序遍历：左 -> 右 -> 根
    可以在前序遍历基础上改造：根->右->左的结果反转
    """
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # 与前序相反：先压左再压右
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]  # 反转

# 测试
print(postorder_iterative(root))  # [4, 5, 2, 6, 3, 1]

层序遍历（BFS） ​

使用队列，一层一层地遍历：

python
from collections import deque

def level_order(root):
    """
    层序遍历（广度优先）
    返回每层的节点值
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level_vals = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level_vals.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_vals)
    
    return result

# 测试
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
print(level_order(root))  # [[1], [2, 3], [4, 5, 6]]

逐行打印 ​

python
def level_order_print(root):
    if not root:
        return
    
    queue = deque([root])
    level = 0
    
    while queue:
        print(f"Level {level}: ", end="")
        for _ in range(len(queue)):
            node = queue.popleft()
            print(node.val, end=" ")
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print()
        level += 1

level_order_print(root)
# Level 0: 1 
# Level 1: 2 3 
# Level 2: 4 5 6

BST（二叉搜索树） ​

BST 的性质：左子树所有节点 < 根节点 < 右子树所有节点

BST 验证 ​

python
def is_valid_bst(root):
    """
    验证二叉树是否是 BST
    中序遍历应该得到有序序列
    """
    stack = []
    inorder = float('-inf')
    curr = root
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        
        curr = stack.pop()
        
        # 必须严格小于
        if curr.val <= inorder:
            return False
        inorder = curr.val
        
        curr = curr.right
    
    return True

BST 搜索 ​

python
def search_bst(root, val):
    """
    在 BST 中搜索值为 val 的节点
    """
    while root:
        if root.val == val:
            return root
        elif val < root.val:
            root = root.left
        else:
            root = root.right
    return None

# 递归版本
def search_bst_recursive(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search_bst_recursive(root.left, val)
    return search_bst_recursive(root.right, val)

BST 插入 ​

python
def insert_into_bst(root, val):
    """
    在 BST 中插入新节点
    """
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    
    return root

二叉树深度 ​

python
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

def min_depth(root):
    """
    计算二叉树的最小深度（从根到最近叶子的节点数）
    """
    if not root:
        return 0
    if not root.left:
        return min_depth(root.right) + 1
    if not root.right:
        return min_depth(root.left) + 1
    
    return min(min_depth(root.left), min_depth(root.right)) + 1

对称二叉树 ​

python
def is_symmetric(root):
    """
    验证二叉树是否对称
    """
    def check(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        
        return (left.val == right.val and 
                check(left.left, right.right) and 
                check(left.right, right.left))
    
    return check(root.left, root.right)

路径总和 ​

python
def has_path_sum(root, target_sum):
    """
    是否有从根到叶子的路径，和等于 target_sum
    """
    if not root:
        return False
    
    # 叶子节点
    if not root.left and not root.right:
        return root.val == target_sum
    
    return (has_path_sum(root.left, target_sum - root.val) or
            has_path_sum(root.right, target_sum - root.val))

所有路径 ​

python
def binary_tree_paths(root):
    """
    返回所有从根到叶子的路径
    """
    if not root:
        return []
    
    if not root.left and not root.right:
        return [str(root.val)]
    
    paths = []
    for path in binary_tree_paths(root.left):
        paths.append(f"{root.val}->{path}")
    for path in binary_tree_paths(root.right):
        paths.append(f"{root.val}->{path}")
    
    return paths

# 测试
print(binary_tree_paths(root))  # ['1->2->4', '1->2->5', '1->3->6']

最近公共祖先（LCA） ​

python
def lowest_common_ancestor(root, p, q):
    """
    找到 p 和 q 的最近公共祖先
    """
    if not root:
        return None
    
    # 如果根就是 p 或 q，直接返回
    if root == p or root == q:
        return root
    
    # 在左右子树中查找
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    # 如果左右都找到了，说明根是 LCA
    if left and right:
        return root
    
    # 否则返回非空的那个
    return left or right

二叉树遍历总结 ​

遍历方式顺序应用场景
前序根-左-右创建/复制树，输出路径
中序左-根-右BST 有序遍历
后序左-右-根删除树，计算深度
层序按层最短路径，树高

[[返回算法首页|algorithm/index]]

Released under the MIT License.

Copyright © 2018-present raopan 饶盼 base on VitePress 2.0.0-alpha.17