前面学的数组、链表、栈、队列、哈希表，数据都是"一条线"排开的。但现实里很多东西天生是分叉的：

  • 公司组织架构：一个 CEO 下面一堆 VP，每个 VP 下面又带几个总监……
  • 文件夹结构：一个目录里有子目录，子目录里还有子目录……
  • 网页的 HTML：<body> 里套 <div>，<div> 里又套 <p>……

这些"一个上级、多个下级"的结构，用一条线表示就很不自然，得用树（tree）。

树是整个算法世界里最重要的数据结构之一，后面要学的堆、二叉搜索树、乃至 AI 里的决策树、语法树，全是从这棵树上长出来的。这一课，我们认识树、遍历树、递归地"玩"树。

一、树是什么：一堆"节点"用边连起来

先记几个术语，用一张家族关系图秒懂：

        A          ← 根节点（root），最上面的那个
       / \
      B   C        ← B、C 是 A 的孩子（children），A 是它们的父节点（parent）
     / \   \
    D   E   F      ← D、E、F 是叶子节点（leaf，没有孩子）
术语含义
根节点 root树最顶端的节点，只有一个
父/子节点有边相连的上下两个节点
叶子 leaf没有任何孩子的节点
深度 depth从根到某节点经过的边数
高度 height从某节点到最远叶子的边数
子树 subtree任意节点连同它下面的所有节点，又构成一棵树

树的本质：一个节点可以指向多个子节点，但每个节点只有一个父节点（根除外），且不能有环。

二、二叉树：每个节点最多两个孩子

如果限定"每个节点最多两个孩子"，就成了二叉树（binary tree）——左孩子 + 右孩子。它是被研究得最透彻的树，也是面试最爱。

在 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
root = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
)

三、遍历二叉树：三种经典顺序

树的"遍历"，就是按某种顺序访问每个节点。二叉树有三种经典遍历，区别只在"根节点什么时候访问"：

  1. 前序（preorder）：根 → 左 → 右
  2. 中序（inorder）：左 → 根 → 右
  3. 后序（postorder）：左 → 右 → 根

对着这棵树看：

        A
       / \
      B   C
     / \
    D   E
  • 前序：A B D E C（先到哪个先记哪个）
  • 中序：D B E A C（左完记根，再右）
  • 后序：D E B C A（左右都完才记根）

三种遍历用递归写，短到不像话——这就是树和递归的"天生一对"：

def preorder(root):
    if not root:
        return
    print(root.val, end=" ")   # 根
    preorder(root.left)        # 左
    preorder(root.right)       # 右

def inorder(root):
    if not root:
        return
    inorder(root.left)         # 左
    print(root.val, end=" ")   # 根
    inorder(root.right)        # 右

def postorder(root):
    if not root:
        return
    postorder(root.left)       # 左
    postorder(root.right)      # 右
    print(root.val, end=" ")   # 根

记忆口诀：前序"根在前"，中序"根在中"，后序"根在后"。

三种遍历分别有什么用？

  • 前序：复制一棵树、序列化保存（先存根，才能重建）
  • 中序：二叉搜索树（BST）的中序遍历，结果是从小到大排好序的！这是它最重要的用途
  • 后序：删除一棵树、算树的高度（先处理完孩子，再处理根）

四、层次遍历：一层一层地走

除了递归的三种，还有一种按层的遍历——层次遍历（level order），它要用到第 2 课学的队列：

        A         层次遍历结果：A B C D E
       / \        （第0层A，第1层B C，第2层D E）
      B   C
     / \
    D   E
from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):   # 每次处理完当前一整层
            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

# 对上面的树，返回 [[1], [2, 3], [4, 5]]

层次遍历的心法：广度优先（BFS）——用队列，一层一层往外扩。它对应的是第 14 课要讲的"图的广度优先搜索"，现在先混个脸熟。

五、递归"玩"树：三行一个经典问题

树的题，几乎全是递归。因为"树的任何子树，本身就是一棵树"——这个自相似性，让递归成了天然解法。

1. 求树的高度

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
    # 树高 = 1（自己）+ 左右子树里更高的那个

2. 判断两棵树是否相同

def is_same(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 is_same(p.left, q.left) and is_same(p.right, q.right)
    # 值相同，还得左右子树都相同

3. 反转二叉树（左右镜像互换）

def invert(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left   # 左右互换
    invert(root.left)
    invert(root.right)
    return root

看这三题的共同套路：递归处理"根 + 左子树 + 右子树"，边界是"空节点"。树的问题，先想清楚"空树怎么办"，再想"根和左右子树怎么组合"，答案就出来了。

六、复杂度小结

对一棵有 n 个节点的二叉树：

操作复杂度说明
遍历（前/中/后序）O(n)每个节点访问一次
层次遍历O(n)每个节点进出队列一次
求高度O(n)递归访问所有节点
递归栈空间O(h)h 是树高，最坏退化成链时是 O(n)

注意最坏情况：如果二叉树退化成一条链（每个节点只有左孩子或只有右孩子），树高 h = n，递归会爆栈，所有"O(h)"的空间都变成 O(n)。这也是为什么后面要学平衡树——保持树"矮胖"，性能才稳。

七、平衡二叉树与红黑树：让树永远"矮胖"

问题：最怕"退化成链"

上一节说过，二叉查找树最怕数据有序地进来——比如按 1、2、3、4、5 顺序插入，树就长成一条斜线，查找退化成 O(n)。

要治这个病，就一个办法：插入、删除时，顺手把树"扶正"，让它保持"矮胖"（平衡）。树一旦平衡，高 h 就是 O(log n)，查找/插入/删除就都能锁死在 O(log n)。

平衡二叉树（AVL）：严格"左右身高差 ≤ 1"

最早的平衡树叫 AVL 树，它立了一条很严的规矩：

任意节点的左子树高度和右子树高度，最多差 1。一旦差超过 1，就通过旋转把树重新扶正。

「旋转」不神秘，就是改变父子关系、让树重新"站正"，本质是几行指针调换：

# 右旋示意（左重右轻时，把左边顶上去）
#     y                x
#    / \              / \
#   x   C    ==>     A   y
#  / \                  / \
# A   B                B   C
def right_rotate(y):
    x = y.left
    y.left = x.right
    x.right = y
    return x          # x 成为新的根

AVL 的好处：查找严格 O(log n)，因为树高被死死压住。代价：规矩太严，每次插入/删除可能要转好几下，写代码的人很痛苦。

红黑树：放宽一点，用"颜色"偷懒

AVL 太较真，于是有了红黑树（Red-Black Tree）——它不再要求"严格平衡"，只要求"大致平衡"，换取更少的旋转，更适合频繁增删的场景。

红黑树的五条规矩（记住前四条就能看懂）：

  1. 每个节点要么红，要么黑。
  2. 根节点永远是黑的。
  3. 每个叶子（空节点）算黑的。
  4. 红色节点的两个孩子必须是黑的（红不能连着红）。
  5. 从任意节点到它所有叶子，经过的黑色节点数量一样多（黑高相等）。

第 5 条是精髓：它保证"最长的路径也不会比最短的路径长到离谱"——最长路径最多是"红黑红黑…"，最短是"全黑"，两者长度最多差 1 倍。所以树高 O(log n)，查找仍是 O(log n)，但插入删除时旋转次数比 AVL 少。

AVL vs 红黑树，怎么选

维度AVL 树红黑树
平衡程度严格（高差 ≤1）大致（最长 ≤ 2×最短）
查找更快一点（树更矮）略慢一点（树稍高）
插入/删除旋转多，慢旋转少，快
适合读多写少（如字典查询）读写都频繁（如数据库索引、map）

一句话记住：AVL 是"书呆子"，规矩死但查得快；红黑树是"灵活派"，稍微松一点、换来增删更省事。

工程里你几乎不用手写红黑树——C++ 的 std::map、Java 的 TreeMap、Linux 内核、数据库的很多索引，底层都是红黑树。Python 标准库没有直接提供，但 sortedcontainers 这类库、以及数据库的 B+ 树思路，都能给你 O(log n) 的有序查找。

八、跳表：不用树，也能 O(log n)

平衡树（AVL、红黑树）能保证查找/插入/删除都是 O(log n)，但写起来很麻烦——旋转、变色、一堆边界情况。有没有更简单的结构也能做到 O(log n)？

有，跳表（Skip List）。它的思路特别"接地气"：

一个有序链表，查找要 O(n)（只能一步步走）。但如果我在链表上面再架几层"索引"，只指向隔几个的节点，就能"跳着走"，把查找降到 O(log n)。

具体做法：

  1. 底层是一个有序链表，存所有元素。
  2. 往上再叠几层"索引链表"，每层只保留下面一层约一半的节点（用抛硬币决定每个节点"升不升到上一层"）。
  3. 查找时从最高层往下走：能跳就跳，跳不动了降一层，最后落到目标附近。
# 跳表概念示意（不实现完整代码，感受"分层索引"即可）
# 底层链表：  1 -> 3 -> 5 -> 7 -> 9 -> 11
# 第 1 层索引：1 -----> 5 -----> 9 ------> 11
# 第 2 层索引：1 -----------> 9 ----------> 11
# 找 7：从第 2 层 1 -> 9（超了，降一层）-> 5 -> 9（超了，降到底层）-> 7 ✅
# 只跳了几步就定位到 7；n 越大，比纯链表省得越多。

为什么是 O(log n)：每层约减半，层数是 O(log n)，每层最多走几步就降层，所以查找是 O(log n)。

跳表 vs 平衡树：

维度跳表平衡树（红黑树等）
查找/插入/删除O(log n)O(log n)
实现难度简单，就是"多层链表"复杂，旋转/变色
范围查询天然支持（从最小值往后扫）中序遍历
额外空间O(n)（索引节点）O(n)

Redis 的有序集合（ZSet）底层就是跳表——工程里"要 O(log n) 又不想写红黑树"时的首选。

九、延伸：线段树与树状数组——区间查询的加速器

前面树的操作，都是一次访问一个节点。但有一类高频问题，树解决得不好：

数组 [3, 1, 4, 1, 5, 9, 2, 6]，反复问"第 2 到第 6 个数的和是多少？"，中间还穿插着"把第 4 个数改成 8"。

如果每次求和都从头加一遍，是 O(n)；改一个数倒是 O(1)。有没有办法区间求和、单点修改都很快？有两个经典结构：树状数组和线段树。

1. 树状数组（Fenwick Tree）：代码极短的前缀和利器

核心思想：维护一个数组 t，其中 t[i] 存的是"以 i 结尾、长度为 lowbit(i) 的一段的和"。lowbit(i) = i & -i，取出 i 二进制里最右边的 1。

class BIT:
    def __init__(self, n):
        self.t = [0] * (n + 1)
        self.n = n
    def add(self, i, v):          # 单点修改：a[i] += v
        while i <= self.n:
            self.t[i] += v
            i += i & -i           # 往上爬
    def sum(self, i):             # 前缀和：a[1..i]
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i           # 往下跳
        return s

bit = BIT(10)
for i, v in enumerate([1, 3, 5, 7, 9, 11], 1):
    bit.add(i, v)
print(bit.sum(5))   # 25（1+3+5+7+9）

区间和 = sum(r) - sum(l-1)。单点修改和前缀查询都是 O(log n)。

2. 线段树（Segment Tree）：能处理"任意区间聚合"

树状数组只能处理"可逆"的运算（求和可减）。线段树更通用：它是一棵每个节点代表一个区间的二叉树，叶子是单个元素，父节点的值 = 两个子节点值的合并（和、最大值、最小值……）。

# 递归建树 + 区间查询（以区间求和为例）
class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)
    def _build(self, arr, node, l, r):
        if l == r:
            self.tree[node] = arr[l]
            return
        mid = (l + r) // 2
        self._build(arr, node*2, l, mid)
        self._build(arr, node*2+1, mid+1, r)
        self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
    def query(self, ql, qr):
        return self._query(1, 0, self.n-1, ql, qr)
    def _query(self, node, l, r, ql, qr):
        if qr < l or r < ql:      # 完全不相交
            return 0
        if ql <= l and r <= qr:   # 完全包含
            return self.tree[node]
        mid = (l + r) // 2
        return self._query(node*2, l, mid, ql, qr) + self._query(node*2+1, mid+1, r, ql, qr)

st = SegTree([1, 3, 5, 7, 9, 11])
print(st.query(1, 4))   # 24（3+5+7+9）

区间查询、区间修改都是 O(log n)，还能支持"区间加/区间最值"等树状数组做不了的运算。

3. 前缀和与差分：不修改 / 不查询时的 O(1) 神器

树状数组/线段树是"查询、修改都要快"时的全能选手。但如果你的需求更单纯，有两个代码更短、跑得更快的 O(1) 技巧：

前缀和（Prefix Sum）：只读不改，反复问区间和。

arr = [3, 1, 4, 1, 5, 9, 2, 6]
pre = [0]
for v in arr:
    pre.append(pre[-1] + v)   # pre[i] = 前 i 个数的和
# 区间 [l, r] 的和 = pre[r+1] - pre[l]
print(pre[6] - pre[1])   # 第 2~6 个数的和 = 1+4+1+5+9 = 20

预处理 O(n)，之后每次区间求和 O(1)。

差分（Diff Array）：反向操作——"频繁区间修改、最后一次性查询"时用它。

arr = [0] * 8
diff = [0] * (len(arr) + 1)
# 给区间 [l, r] 整体 +v：diff[l] += v; diff[r+1] -= v
def add(l, r, v):
    diff[l] += v
    diff[r + 1] -= v

add(1, 4, 5)   # 第 1~4 个元素 +5
add(3, 6, 2)   # 第 3~6 个元素 +2
# 最后做一次前缀和还原：
cur = 0
for i in range(len(arr)):
    cur += diff[i]
    arr[i] = cur
print(arr)   # [0, 5, 5, 7, 7, 2, 2, 0]

每次修改 O(1)，最后一次性还原 O(n)。"区间加"大量出现时，差分比线段树简洁得多。

记忆口诀：前缀和管"查得快"，差分管"改得快"；又要查又要改，才上树状数组/线段树。

用在哪儿

场景用哪个
排行榜、前缀和树状数组（短、快）
区间最值、区间求和、带修改线段树（通用）
数据流统计、逆序对树状数组

记住：树状数组/线段树 = 把"区间"也变成树上的节点，让"一次算一段"从 O(n) 变成 O(log n)。

十、动手时间 🎯

实验 1：搭一棵树，跑三种遍历

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

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

def preorder(r):
    if not r: return
    print(r.val, end=" ")
    preorder(r.left); preorder(r.right)

def inorder(r):
    if not r: return
    inorder(r.left)
    print(r.val, end=" ")
    inorder(r.right)

def postorder(r):
    if not r: return
    postorder(r.left); postorder(r.right)
    print(r.val, end=" ")

print("前序:", end=" "); preorder(root); print()
print("中序:", end=" "); inorder(root);  print()
print("后序:", end=" "); postorder(root); print()

对照手工结果，看看三种顺序差在哪。

实验 2：从数组递归建树（了解"树是怎么来的"）

def build(nums, i):
    # 用数组下标 i 表示节点位置，2i+1 左孩子、2i+2 右孩子
    if i >= len(nums) or nums[i] is None:
        return None
    node = TreeNode(nums[i])
    node.left = build(nums, 2 * i + 1)
    node.right = build(nums, 2 * i + 2)
    return node

# [1,2,3,4,5] 表示：
#       1
#      / \
#     2   3
#    / \
#   4   5
r = build([1, 2, 3, 4, 5], 0)
inorder(r)   # 4 2 5 1 3

这个"下标 2i+1 / 2i+2"的规则，正是堆（后面主角）的存储方式，先记住它。

实验 3：统计叶子节点个数

def count_leaves(root):
    if not root:
        return 0
    if not root.left and not root.right:   # 没有孩子，就是叶子
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

print(count_leaves(r))   # 3（节点 4、5、3）

实验 4（挑战）：判断一棵树是否"平衡"

平衡 = 任意节点左右子树高度差不超过 1。

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        if lh == -1 or rh == -1 or abs(lh - rh) > 1:
            return -1     # 用 -1 标记"已经不平衡"
        return 1 + max(lh, rh)
    return height(root) != -1

# 上面的树 r 是平衡的；自己搭一棵不平衡的试试

体会：这个"递归返回时顺便带信息"的技巧（返回 -1 表示状态），在树的题里极常用。

十一、小结

  1. 树是"一个上级多个下级"的层级结构，二叉树每个节点最多两个孩子，节点用类表示（val + left + right）。
  2. 三种递归遍历记"根在哪"：前序根在前、中序根在中（BST 里中序=有序）、后序根在后；层次遍历用队列一层层走。
  3. 树的题 = 递归处理"根 + 左右子树"，边界是空节点——求高度、判相同、反转，全是这个套路。

先别急着往后翻，把三种遍历和"求高度/数叶子"敲熟，树的手感就长在你脑子里了。

标签: none

添加新评论