树与二叉树

树的基本概念

• 节点（Node）树的基本单元，包含数据和指向子节点的指针
• 根（Root）没有父节点的唯一节点，是树的起始点
• 叶节点（Leaf）没有子节点的节点
• 深度（Depth）从根节点到该节点的边数；根节点深度为 0
• 高度（Height）从该节点到最深叶节点的最长路径的边数；叶节点高度为 0
• 度（Degree）节点拥有的子节点数量
• 子树（Subtree）某节点及其所有后代组成的树

二叉树定义与类型

二叉树每个节点最多有两个子节点（左子节点、右子节点）。

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,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None,       TreeNode(6)))

类型	定义	性质
满二叉树	每个节点有 0 或 2 个子节点	叶节点数 = 内节点数 + 1
完全二叉树	除最后一层外其余层全满，最后一层节点靠左	可用数组紧凑存储，堆的基础
平衡二叉树	左右子树高度差 ≤ 1（对每个节点成立）	AVL 树、红黑树，保证 O(log n)
二叉搜索树	左子树所有值 < 根值 < 右子树所有值	中序遍历是有序序列

树的遍历（重中之重）

树的遍历是面试最高频考点，必须烂熟于心。四种遍历方式，每种都要掌握递归和迭代两种写法。

前序遍历（根 → 左 → 右）

访问顺序：先处理当前节点，再递归左右子树。用于复制树、序列化树。

# 递归版 — 代码简洁，理解遍历顺序
def preorder_recursive(root) -> list:
    if not root:
        return []
    return [root.val] + preorder_recursive(root.left) + preorder_recursive(root.right)

# 迭代版 — 显式用栈模拟递归调用栈
def preorder_iterative(root) -> list:
    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

中序遍历（左 → 根 → 右）

对 BST 做中序遍历，得到的是升序序列。这是 BST 最重要的性质之一。

# 递归版
def inorder_recursive(root) -> list:
    if not root:
        return []
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

# 迭代版 — 中序遍历的迭代版是最经典的栈应用
def inorder_iterative(root) -> list:
    result, stack = [], []
    cur = root
    while cur or stack:
        # 一路向左走到底，将沿途节点压栈
        while cur:
            stack.append(cur)
            cur = cur.left
        # 弹出栈顶节点：此时它的左子树已全部访问
        cur = stack.pop()
        result.append(cur.val)   # 访问当前节点（根）
        cur = cur.right          # 转向右子树
    return result

后序遍历（左 → 右 → 根）

访问当前节点前，必须先访问完两棵子树。用于计算目录大小、删除树节点。

# 递归版
def postorder_recursive(root) -> list:
    if not root:
        return []
    return postorder_recursive(root.left) + postorder_recursive(root.right) + [root.val]

# 迭代版 — 技巧：前序改造（根→右→左），再反转结果得（左→右→根）
def postorder_iterative(root) -> list:
    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]          # 反转得到后序结果

层序遍历（BFS）

按层次从上到下、从左到右访问节点。使用队列实现。

from collections import deque

# 返回每层节点组成的二维列表
def level_order(root) -> list:
    if not root:
        return []
    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)    # 当前层的节点数
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(level)

    return result

# 对示例树 result = [[1], [2, 3], [4, 5, 6]]

二叉搜索树（BST）

BST 的核心性质：对任意节点，左子树所有值 < 节点值 < 右子树所有值。

# BST 查找 — O(h)，平衡时 O(log n)
def search_bst(root, target):
    if not root or root.val == target:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)

# BST 插入
def insert_bst(root, val):
    if not root:
        return TreeNode(val)   # 找到插入位置
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
    return root   # 值已存在，不重复插入

# BST 删除（最复杂的操作）
def delete_bst(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete_bst(root.left, key)
    elif key > root.val:
        root.right = delete_bst(root.right, key)
    else:   # 找到要删除的节点
        if not root.left:  return root.right  # 无左子树
        if not root.right: return root.left   # 无右子树
        # 有两个子树：用右子树最小值（中序后继）替换
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val                  # 替换值
        root.right = delete_bst(root.right, successor.val)  # 删除后继
    return root

堆（Heap）

堆是一种特殊的完全二叉树，满足堆性质：最大堆中每个节点的值 ≥ 其子节点的值；最小堆则 ≤。

# 完全二叉树可用数组表示（下标从 0 开始）
# 下标 i 的节点：父节点 (i-1)//2，左子节点 2i+1，右子节点 2i+2

def heapify_down(arr, n, i):
    """将下标 i 的元素向下调整，维护最大堆性质"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify_down(arr, n, largest)  # 递归调整

def heap_sort(arr):
    n = len(arr)
    # 建堆：从最后一个非叶节点开始向上调整
    for i in range(n // 2 - 1, -1, -1):
        heapify_down(arr, n, i)
    # 排序：逐步将堆顶（最大值）移到末尾
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 堆顶与末尾交换
        heapify_down(arr, i, 0)          # 重新堆化
    return arr

建堆O(n) 堆排序O(n log n) 插入/删除O(log n)

字典树（Trie）

Trie（前缀树）是一种多叉树，专门用于字符串的高效存储和检索。每个节点表示一个字符，从根到某个节点的路径表示一个字符串前缀。

应用：搜索自动补全、IP 路由、拼写检查、词频统计。

class TrieNode:
    def __init__(self):
        self.children = {}    # 字符 → 子节点
        self.is_end = False  # 是否是某个单词的结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True   # 标记单词结尾

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end   # 必须是完整单词

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True   # 只需到达前缀末尾即可

# 时间复杂度：所有操作均为 O(L)，L 为字符串长度

经典题目详解

二叉树最大深度

def max_depth(root) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
# 递归思路："树的深度 = max(左子树深度, 右子树深度) + 1"

对称二叉树

def is_symmetric(root) -> bool:
    def mirror(left, right) -> bool:
        if not left and not right: return True
        if not left or not right:  return False
        return (left.val == right.val
                and mirror(left.left, right.right)
                and mirror(left.right, right.left))
    return mirror(root.left, root.right)

路径总和（是否存在根到叶的路径）

def has_path_sum(root, target: int) -> bool:
    if not root:
        return False
    if not root.left and not root.right:  # 叶节点
        return root.val == target
    remaining = target - root.val
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

序列化与反序列化

class Codec:
    def serialize(self, root) -> str:
        """前序遍历，None 用 '#' 表示"""
        if not root:
            return '#'
        return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"

    def deserialize(self, data: str):
        nodes = iter(data.split(','))

        def build():
            val = next(nodes)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node

        return build()