树与图

树是"有层次的链表"，图是"多对多的树"。树的遍历套路、图的最短路/连通性题感，是算法面试的重头戏。

一、树的基础概念

1.1 树的术语

节点、根、叶子、父/子、兄弟、祖先/后代、子树、高度（从下往上数边）、深度（从上往下数边）、层。
二叉树：每个节点最多两个孩子的树，分左子树/右子树。

        A          ← 根 root（深度 0）
       / \
      B   C        ← B、C 是 A 的孩子；B 的左孩子
     / \   \
    D   E   F      ← D/E/F 为叶子
高度：整棵树高度 = 3（最长路径 A→B→E 的边数）

        A          ← 根 root（深度 0）
       / \
      B   C        ← B、C 是 A 的孩子；B 的左孩子
     / \   \
    D   E   F      ← D/E/F 为叶子
高度：整棵树高度 = 3（最长路径 A→B→E 的边数）

1.2 满二叉树与完全二叉树

满二叉树：除叶子外每个节点都有两个孩子，且叶子全在同一层。
完全二叉树：除最后一层外每层都满，最后一层节点靠左排列（堆就是这个形状）。

满二叉树(节点 2^h-1)        完全二叉树（最后一层靠左）
      1                         1
     / \                       / \
    2   3                     2   3
   / \ / \                   / \
  4  5 6  7                 4   5

满二叉树(节点 2^h-1)        完全二叉树（最后一层靠左）
      1                         1
     / \                       / \
    2   3                     2   3
   / \ / \                   / \
  4  5 6  7                 4   5

1.3 树的存储方式

链式（刷题最常见）：TreeNode(val, left, right)。
数组：完全二叉树可用数组，下标 i 的左孩子 2i+1、右孩子 2i+2、父 (i-1)//2（堆的实现）。

二、二叉树的遍历（重点）

2.1 前中后序遍历：递归模板

前序（根→左→右）、中序（左→根→右）、后序（左→右→根），区别只在访问根的时机。

python

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

def inorder(root):          # BST 中序 = 升序序列
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

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

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

def inorder(root):          # BST 中序 = 升序序列
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

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

2.2 前序遍历：迭代（显式栈）

手动用栈模拟系统栈：先压右孩子再压左孩子，弹出即访问。

python

def preorder_iter(root):
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        if not node: continue
        res.append(node.val)
        stack.append(node.right)   # 先右后左，弹栈才是左先出
        stack.append(node.left)
    return res

def preorder_iter(root):
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        if not node: continue
        res.append(node.val)
        stack.append(node.right)   # 先右后左，弹栈才是左先出
        stack.append(node.left)
    return res

2.3 中序遍历：迭代（一路向左）

经典写法：不断把左孩子压栈，弹出后访问，再转向右子树。

python

def inorder_iter(root):
    res, stack, cur = [], [], root
    while stack or cur:
        while cur:                 # 一路向左压栈
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()          # 弹栈访问
        res.append(cur.val)
        cur = cur.right            # 转向右子树
    return res

def inorder_iter(root):
    res, stack, cur = [], [], root
    while stack or cur:
        while cur:                 # 一路向左压栈
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()          # 弹栈访问
        res.append(cur.val)
        cur = cur.right            # 转向右子树
    return res

2.4 后序遍历：迭代

技巧：前序是"根左右"，把左右压栈顺序反过来得到"根右左"，再整体反转即"左右根"。

python

def postorder_iter(root):
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        if not node: continue
        res.append(node.val)
        stack.append(node.left)    # 与 2.2 相反
        stack.append(node.right)
    return res[::-1]               # 反转得到后序

def postorder_iter(root):
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        if not node: continue
        res.append(node.val)
        stack.append(node.left)    # 与 2.2 相反
        stack.append(node.right)
    return res[::-1]               # 反转得到后序

2.5 层序遍历：BFS 队列

用队列逐层取出；要求"按层分组"时，每轮先记录当前队列长度。

python

from collections import deque

def level_order(root):
    res = []
    if not root: return res
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):    # 关键：一次取完一整层
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

from collections import deque

def level_order(root):
    res = []
    if not root: return res
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):    # 关键：一次取完一整层
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

2.6 遍历复杂度对比表

遍历方式	递归	迭代辅助	时间	空间(递归栈/辅助)
前序	✓	栈	O(n)	O(树高)，最坏 O(n)
中序	✓	栈	O(n)	O(树高)
后序	✓	栈/双栈	O(n)	O(树高)
层序	不便	队列	O(n)	O(层最大宽度)

四种遍历都访问每个节点一次，时间复杂度都是 O(n)；差别只在空间与输出顺序。

2.7 由遍历序列还原二叉树

前序 + 中序：前序第一个是根，在中序中定位根 → 左右子树长度确定 → 递归。
后序 + 中序：同理，后序最后一个是根。
只给前序+后序不能唯一确定二叉树（缺中序信息）。
代表题：LeetCode 105（前中序还原）、106（中后序还原）。

三、二叉搜索树（BST）

3.1 定义与性质

左子树所有节点 < 根 < 右子树所有节点，且左右子树也满足（递归定义）。
关键推论：中序遍历得到升序序列（验证 BST 与求第 K 小都用它）。

       8
      / \
     3   10        ← 8 的左子树全 < 8，右子树全 > 8
    / \    \
   1   6    14

       8
      / \
     3   10        ← 8 的左子树全 < 8，右子树全 > 8
    / \    \
   1   6    14

3.2 查找 / 插入 / 删除

操作	平均(平衡)	最坏(退化链)	思路
查找	O(log n)	O(n)	比大小决定走左/右
插入	O(log n)	O(n)	找到空位挂上叶子
删除	O(log n)	O(n)	分三种情况见下

删除三情况：无孩子直接删；一个孩子用孩子顶替；两个孩子用**右子树最小节点（中序后继）**顶替再删。

3.3 中序遍历有序的特性

利用此性质可做：BST 转升序数组、第 K 小元素（中序数到 K）、两数之和（转数组后双指针）。

3.4 验证 BST 的易错点

错误做法：只比较当前节点与左右孩子——子树里可能存在越界的远亲节点。
正确做法：递归传上下界 (lo, hi)，或中序遍历检查是否严格递增。

python

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root: return True
    if not (lo < root.val < hi): return False
    return (is_valid_bst(root.left, lo, root.val)
            and is_valid_bst(root.right, root.val, hi))

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root: return True
    if not (lo < root.val < hi): return False
    return (is_valid_bst(root.left, lo, root.val)
            and is_valid_bst(root.right, root.val, hi))

四、平衡树概念

4.1 为什么需要平衡

BST 在有序插入时会退化成链表（高度 n），操作变 O(n)。
平衡树通过旋转/变色让高度维持在 O(log n)，从而保证操作 O(log n)。

4.2 AVL：严格平衡

定义：每个节点的左右子树高度差绝对值 ≤ 1（平衡因子）。
失衡用四种旋转修正：LL/RR（单旋）、LR/RL（双旋）。
优点：严格平衡、查找快；缺点：插入删除频繁旋转，工程实现重。

4.3 红黑树：弱平衡

定义要点：节点红/黑、根黑、红节点孩子必黑、任一节点到其叶子的路径黑节点数相同。
效果：最长路径不超过最短路径的 2 倍，仍是 O(log n)。
优点：插入删除旋转次数少（最多 2 次旋转+变色）；缺点：不如 AVL 查找快。
工程取舍：读多写少选 AVL，读写均衡/写多选红黑树。

4.4 工程里的平衡树

Java：TreeMap/TreeSet 底层是红黑树（有序，支持 ceiling/floor）。
C++ std::map 红黑树；数据库 B+ 树是另一种多路平衡结构（见数据库笔记）。

五、堆与优先队列（树视角）

5.1 二叉堆是"完全二叉树"

堆在逻辑上是完全二叉树、物理是数组（见常用数据结构第七章）。
大顶堆父 ≥ 子，小顶堆父 ≤ 子；堆不保证兄弟间有序（弱序）。

5.2 堆的核心操作与复杂度

操作	复杂度	说明
取最值	O(1)	永远在堆顶（数组下标 0）
push	O(log n)	尾部插入 + 上浮
pop	O(log n)	堆顶与末尾交换 + 下沉
建堆	O(n)	自底向上逐个下沉
堆排序	O(n log n)	反复 pop 堆顶

题感：题目出现「第 K 大/小」「前 K 个」「动态最值」「合并有序序列」→ 优先队列。

六、图的基础与表示

6.1 基本分类

有向图 / 无向图；带权图 / 无权图；连通 / 不连通；有环 / 无环（DAG 有向无环图）。
常用术语：度（无向）、入度/出度（有向）、路径、环、连通分量。

6.2 邻接矩阵

matrix[i][j] 表示 i→j 是否有边（或权重），无向图沿对角线对称。

   0  1  2
0 [0, 1, 1]        matrix[0][1]=1 → 0→1 有边
1 [1, 0, 0]
2 [1, 0, 0]

   0  1  2
0 [0, 1, 1]        matrix[0][1]=1 → 0→1 有边
1 [1, 0, 0]
2 [1, 0, 0]

特点	值
判断两点是否有边	O(1)
遍历某点所有邻居	O(n)
空间	O(n²)
适用	稠密图、点数小（≤1000）如 Floyd

6.3 邻接表

每个顶点一个列表/集合，存它的邻居（或 (邻居, 权重)）。

0: [1, 2]
1: [0]          ← 0 的邻居是 1、2
2: [0]

0: [1, 2]
1: [0]          ← 0 的邻居是 1、2
2: [0]

特点	值
判断两点是否有边	O(度)，最坏 O(n)
遍历某点所有邻居	O(度)
空间	O(n+m)（m 为边数）
适用	稀疏图，绝大多数算法题

6.4 两种表示对比与选择

维度	邻接矩阵	邻接表
空间	O(n²)	O(n+m)
判边	O(1)	O(度)
遍历邻居	O(n)	O(度)
加/删边	O(1)	O(1)（若用哈希集合）
结论	点少边多	点多边少，默认首选

刷题建议：输入给边列表时，先转成邻接表 g = [[] for _ in range(n)]。

七、图的遍历：DFS 与 BFS

7.1 DFS（深度优先，递归/栈）

一条路走到底再回头（回溯）；适合求路径、连通分量、拓扑、环检测。

python

def dfs(g, start):
    seen = set()
    def visit(u):
        if u in seen: return
        seen.add(u)
        for v in g[u]:
            visit(v)
    visit(start)

def dfs(g, start):
    seen = set()
    def visit(u):
        if u in seen: return
        seen.add(u)
        for v in g[u]:
            visit(v)
    visit(start)

7.2 BFS（广度优先，队列）

逐层扩散，第一次到达某节点时一定是最短步数（无权图）。

python

from collections import deque

def bfs(g, start):
    seen, q = {start}, deque([start])
    step = 0
    while q:
        for _ in range(len(q)):        # 按层处理，可数最短步数
            u = q.popleft()
            for v in g[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        step += 1
    return step

from collections import deque

def bfs(g, start):
    seen, q = {start}, deque([start])
    step = 0
    while q:
        for _ in range(len(q)):        # 按层处理，可数最短步数
            u = q.popleft()
            for v in g[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        step += 1
    return step

7.3 复杂度与 visited 记录

遍历	时间	空间	说明
DFS	O(n+m)	O(n) 栈/最坏深度	注意别把图当树漏 visited
BFS	O(n+m)	O(n) 队列	队列最大为最宽层

树的 DFS 不需要 visited（无环）；图必须 visited，否则死循环或指数重复。
处理网格/迷宫：四个方向扩散，可直接用坐标数组 [(1,0),(-1,0),(0,1),(0,-1)]。

八、拓扑排序

8.1 应用场景与前提

前提：有向无环图 DAG。作用：给依赖关系排出线性顺序（课程表、构建依赖、任务调度）。
图里有环则无拓扑序（即存在循环依赖）。

8.2 Kahn 算法（BFS + 入度）

python

from collections import deque

def topo_sort(n, edges):             # edges: 边列表 [a,b] 表示 a→b
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:
        g[a].append(b)
        indeg[b] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    res = []
    while q:
        u = q.popleft()
        res.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return res if len(res) == n else []   # 长度不足 → 有环

from collections import deque

def topo_sort(n, edges):             # edges: 边列表 [a,b] 表示 a→b
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:
        g[a].append(b)
        indeg[b] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    res = []
    while q:
        u = q.popleft()
        res.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return res if len(res) == n else []   # 长度不足 → 有环

8.3 环检测

Kahn 排完后结果数 < n 说明有环；DFS 用三色标记（0 未访问/1 访问中/2 已完成）也可判环。
复杂度：O(n+m)。

九、最短路径：Dijkstra

9.1 思想与前提

前提：边权非负的单源最短路。思想 = BFS 的加权版 + 贪心：每次从未确定集合里选当前距离最小的节点松弛它的邻居。
用优先队列（小顶堆）取"当前距离最小"→ 堆优化 Dijkstra。

python

import heapq

def dijkstra(g, start, n):           # g[u] = [(v, w), ...]
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]                # (距离, 节点)，小顶堆
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:              # 懒惰删除：旧记录跳过
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

import heapq

def dijkstra(g, start, n):           # g[u] = [(v, w), ...]
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]                # (距离, 节点)，小顶堆
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:              # 懒惰删除：旧记录跳过
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

9.2 复杂度对比

版本	时间	空间
朴素（每次扫全部未定点）	O(n²)	O(n)
堆优化	O((n+m) log n)	O(n+m)

负权边不能用 Dijkstra → Bellman-Ford/SPFA；多源最短路 → Floyd（O(n³)，邻接矩阵）。
题感：网格地图求最小体力/最少花费 → 往往就是 Dijkstra（即使格子看起来像迷宫）。

十、并查集（Union-Find）

10.1 核心思想

用一棵"父指针树"表示集合，支持两个操作：查（find，找根）与并（union，把两个根连一起）。
适用：动态连通性——判断两个点是否连通、统计连通分量个数（省份数量、岛屿连通、冗余连接）。

初始:  0  1  2  3
union(0,1), union(2,3):
    0      2
     \      \
      1      3
find(1) = 0, find(3) = 2

初始:  0  1  2  3
union(0,1), union(2,3):
    0      2
     \      \
      1      3
find(1) = 0, find(3) = 2

10.2 路径压缩与按秩合并

路径压缩：find 时把路径上节点直接挂到根，树变矮。
按秩合并（按大小/高度）：小的树挂到大树上。
两者结合后单次操作近似 O(α(n))（反阿克曼函数，可视为常数）。

10.3 模板

python

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n               # 连通分量个数
    def find(self, x):               # 路径压缩（迭代版）
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):           # 按 size 合并
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n               # 连通分量个数
    def find(self, x):               # 路径压缩（迭代版）
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):           # 按 size 合并
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1

10.4 连通分量类题感

题目信号	并查集用法
求连通分量个数	初始 count=n，每成功 union 一次 count-1
判断两节点是否相连	`find(a) == find(b)`
冗余连接（图里删掉一条边成树）	加边前先查是否已连通，是则该边冗余
等价关系分组	把"相等/同组"关系全部 union

复杂度：近似 O(m·α(n))，m 为操作数；内存 O(n)。

十一、树与图题感速查表

题目信号	套路	复杂度参考
二叉树遍历/深度/路径和	递归或栈迭代	O(n)
逐层输出/最短步数/最小高度	BFS	O(n) 或 O(n+m)
所有路径/排列组合式枚举	DFS 回溯	指数级，注意剪枝
BST 第 K 小/验证	中序遍历	O(n) 或 O(h+k)
课程表/依赖顺序/是否有环	拓扑排序 Kahn	O(n+m)
无权图最短路	BFS	O(n+m)
带权非负最短路	Dijkstra + 堆	O((n+m) log n)
连通性/朋友圈/岛屿数量	DFS/BFS 或并查集	O(n+m) / O(m·α)
迷宫最短路径/最少步	BFS 状态搜索	与状态数线性相关

树与图 ​

一、树的基础概念 ​

1.1 树的术语 ​

1.2 满二叉树与完全二叉树 ​

1.3 树的存储方式 ​

二、二叉树的遍历（重点） ​

2.1 前中后序遍历：递归模板 ​

2.2 前序遍历：迭代（显式栈） ​

2.3 中序遍历：迭代（一路向左） ​

2.4 后序遍历：迭代 ​

2.5 层序遍历：BFS 队列 ​

2.6 遍历复杂度对比表 ​

2.7 由遍历序列还原二叉树 ​

三、二叉搜索树（BST） ​

3.1 定义与性质 ​

3.2 查找 / 插入 / 删除 ​

3.3 中序遍历有序的特性 ​

3.4 验证 BST 的易错点 ​

四、平衡树概念 ​

4.1 为什么需要平衡 ​

4.2 AVL：严格平衡 ​

4.3 红黑树：弱平衡 ​

4.4 工程里的平衡树 ​

五、堆与优先队列（树视角） ​

5.1 二叉堆是"完全二叉树" ​

5.2 堆的核心操作与复杂度 ​

六、图的基础与表示 ​

6.1 基本分类 ​

6.2 邻接矩阵 ​

6.3 邻接表 ​

6.4 两种表示对比与选择 ​

七、图的遍历：DFS 与 BFS ​

7.1 DFS（深度优先，递归/栈） ​

7.2 BFS（广度优先，队列） ​

7.3 复杂度与 visited 记录 ​

八、拓扑排序 ​

8.1 应用场景与前提 ​

8.2 Kahn 算法（BFS + 入度） ​

8.3 环检测 ​

九、最短路径：Dijkstra ​

9.1 思想与前提 ​

9.2 复杂度对比 ​

十、并查集（Union-Find） ​

10.1 核心思想 ​

10.2 路径压缩与按秩合并 ​

10.3 模板 ​

10.4 连通分量类题感 ​

十一、树与图题感速查表 ​

树与图

一、树的基础概念

1.1 树的术语

1.2 满二叉树与完全二叉树

1.3 树的存储方式

二、二叉树的遍历（重点）

2.1 前中后序遍历：递归模板

2.2 前序遍历：迭代（显式栈）

2.3 中序遍历：迭代（一路向左）

2.4 后序遍历：迭代

2.5 层序遍历：BFS 队列

2.6 遍历复杂度对比表

2.7 由遍历序列还原二叉树

三、二叉搜索树（BST）

3.1 定义与性质

3.2 查找 / 插入 / 删除

3.3 中序遍历有序的特性

3.4 验证 BST 的易错点

四、平衡树概念

4.1 为什么需要平衡

4.2 AVL：严格平衡

4.3 红黑树：弱平衡

4.4 工程里的平衡树

五、堆与优先队列（树视角）

5.1 二叉堆是"完全二叉树"

5.2 堆的核心操作与复杂度

六、图的基础与表示

6.1 基本分类

6.2 邻接矩阵

6.3 邻接表

6.4 两种表示对比与选择

七、图的遍历：DFS 与 BFS

7.1 DFS（深度优先，递归/栈）

7.2 BFS（广度优先，队列）

7.3 复杂度与 visited 记录

八、拓扑排序

8.1 应用场景与前提

8.2 Kahn 算法（BFS + 入度）

8.3 环检测

九、最短路径：Dijkstra

9.1 思想与前提

9.2 复杂度对比

十、并查集（Union-Find）

10.1 核心思想

10.2 路径压缩与按秩合并

10.3 模板

10.4 连通分量类题感

十一、树与图题感速查表