> ## Content Index
> Fetch the complete content index at: https://blog.vercanti.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 数据结构完全参考
- URL: https://blog.vercanti.com/shu-ju-jie-gou-wan-quan-can-kao/
- Published: 2026-08-28T14:35:45.000Z
- Updated: 2026-08-28T14:59:32.000Z
- Description: Python list 是动态数组（Dynamic Array）： 推论：需要频繁头部操作时，用 collections.deque 替代 list。 循环链表将尾节点的 next 指向头节点。常见于约瑟夫环问题。使用时注意遍历终止条件应以初始节点为准，否则会无限循环。 栈遵循 LIFO（后进先出）原则。 队列遵循 FIFO（先进先出）原则。 Python heapq 是最小堆。实现最大堆时将值取反。 单调栈维护一个单调递增或递减的栈，用于求"下一个更大/更小元素"。 单调队列用于滑动窗口最值问题，队列中元素单调递减（求最大值）或单调递增（求最小值）。
- Author: yellowdog
- Tags: 算法与数据结构

> 官方文档：<https://wiki.python.org/moin/TimeComplexity>  
> 适用版本：Python 3.12（2026-05-07 核实）

## 时间复杂度速查表

### 按数据结构分组

| 数据结构      | 访问       | 查找       | 插入（头/尾）       | 删除（头/尾）         | 空间      |
| --------- | -------- | -------- | ------------- | --------------- | ------- |
| 数组（Array） | O(1)     | O(n)     | O(n) / O(1)\* | O(n) / O(1)\*   | O(n)    |
| 单链表       | O(n)     | O(n)     | O(1) / O(n)   | O(1)\*\* / O(n) | O(n)    |
| 双链表       | O(n)     | O(n)     | O(1) / O(1)   | O(1) / O(1)     | O(n)    |
| 栈         | O(n)     | O(n)     | — / O(1)      | — / O(1)        | O(n)    |
| 队列        | O(n)     | O(n)     | O(1) / —      | — / O(1)        | O(n)    |
| 哈希表       | —        | O(1) 均摊  | O(1) 均摊       | O(1) 均摊         | O(n)    |
| BST（平衡）   | O(log n) | O(log n) | O(log n)      | O(log n)        | O(n)    |
| 堆         | O(1) 最值  | O(n)     | O(log n)      | O(log n)        | O(n)    |
| Trie      | —        | O(m)     | O(m)          | O(m)            | O(n\*m) |

> \* Python `list` 尾部 append 均摊 O(1)，头部 insert(0, x) 为 O(n)  
> \*\* 需持有节点引用时才能 O(1)

---

## 数组与链表

### 对比表格

| 操作     | Python list（动态数组） | 单链表          | 双链表          |
| ------ | ----------------- | ------------ | ------------ |
| 按索引访问  | O(1)              | O(n)         | O(n)         |
| 尾部插入   | O(1) 均摊           | O(n)（无尾指针）   | O(1)（有尾指针）   |
| 头部插入   | O(n)              | O(1)         | O(1)         |
| 任意位置插入 | O(n)              | O(1)（已有节点引用） | O(1)（已有节点引用） |
| 按值查找   | O(n)              | O(n)         | O(n)         |
| 内存布局   | 连续内存，缓存友好         | 离散节点，指针开销    | 离散节点，双向指针    |

### Python list 的底层实现

Python `list` 是动态数组（Dynamic Array）：

- 底层为 C 数组，存储对象指针
- 容量不足时按约 1.125 倍扩容（CPython 实现），重新分配内存并复制
- 扩容均摊后 append 为 O(1)
- `list.insert(0, x)` 需整体右移，为 O(n)
- `list.pop()` 尾部删除 O(1)，`list.pop(0)` 头部删除 O(n)

```python
import sys

lst = []
for i in range(10):
    lst.append(i)
    # sys.getsizeof 返回当前分配的内存字节数
    print(f"len={len(lst)}, allocated_bytes={sys.getsizeof(lst)}")

```

推论：需要频繁头部操作时，用 `collections.deque` 替代 `list`。

### 单链表实现

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.dummy = ListNode(0)  # 哨兵节点，简化边界处理
        self.size = 0

    def append(self, val):
        node = self.dummy
        while node.next:
            node = node.next
        node.next = ListNode(val)
        self.size += 1

    def prepend(self, val):
        new_node = ListNode(val, self.dummy.next)
        self.dummy.next = new_node
        self.size += 1

    def delete(self, val):
        node = self.dummy
        while node.next:
            if node.next.val == val:
                node.next = node.next.next
                self.size -= 1
                return True
            node = node.next
        return False

    def to_list(self):
        result = []
        node = self.dummy.next
        while node:
            result.append(node.val)
            node = node.next
        return result

```

### 双链表实现

```python
class DListNode:
    def __init__(self, val=0):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = DListNode()  # 哨兵头
        self.tail = DListNode()  # 哨兵尾
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def _insert_after(self, node, val):
        new_node = DListNode(val)
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node
        self.size += 1
        return new_node

    def append(self, val):
        return self._insert_after(self.tail.prev, val)

    def prepend(self, val):
        return self._insert_after(self.head, val)

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

```

### 循环链表

循环链表将尾节点的 `next` 指向头节点。常见于约瑟夫环问题。使用时注意遍历终止条件应以初始节点为准，否则会无限循环。

---

## 栈与队列

### 栈

栈遵循 LIFO（后进先出）原则。

#### 用 list 实现

```python
stack = []
stack.append(1)   # 入栈
stack.append(2)
top = stack[-1]   # 查看栈顶：2
val = stack.pop() # 出栈：2

```

#### 用 collections.deque 实现（线程安全版）

```python
from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
val = stack.pop()  # 从右侧弹出

```

> `deque` 两端操作均为 O(1)，但随机访问为 O(n)。纯栈场景下 `list` 与 `deque` 性能接近，`deque` 更安全。

### 队列

队列遵循 FIFO（先进先出）原则。

#### collections.deque

```python
from collections import deque

queue = deque()
queue.append(1)    # 入队（右侧）
queue.append(2)
val = queue.popleft()  # 出队（左侧）：1

```

#### queue.Queue（线程安全）

```python
import queue

q = queue.Queue(maxsize=0)  # maxsize=0 表示无限容量
q.put(1)
q.put(2)
val = q.get()  # 阻塞等待

```

| 参数                | 类型    | 默认值  | 说明                 |
| ----------------- | ----- | ---- | ------------------ |
| maxsize           | int   | 0    | 队列最大容量，0 表示无限制     |
| block (get/put)   | bool  | True | 是否阻塞等待             |
| timeout (get/put) | float | None | 阻塞超时秒数，None 表示永久等待 |

#### 优先队列（heapq）

Python `heapq` 是最小堆。实现最大堆时将值取反。

```python
import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # 1，最小值优先

# 最大堆：存入负值
max_heap = []
for val in [3, 1, 2]:
    heapq.heappush(max_heap, -val)
print(-heapq.heappop(max_heap))  # 3

```

| 函数                      | 参数                    | 说明                 |
| ----------------------- | --------------------- | ------------------ |
| heappush(heap, item)    | heap: list, item: any | 推入元素，保持堆不变性        |
| heappop(heap)           | heap: list            | 弹出最小元素             |
| heappushpop(heap, item) | heap: list, item: any | 推入后立即弹出最小值，比分开调用略快 |
| heapreplace(heap, item) | heap: list, item: any | 先弹出再推入，堆不能为空       |
| heapify(x)              | x: list               | 将列表原地转为堆，O(n)      |
| nlargest(n, iterable)   | n: int, iterable      | 返回最大的 n 个元素        |
| nsmallest(n, iterable)  | n: int, iterable      | 返回最小的 n 个元素        |

### 单调栈

单调栈维护一个单调递增或递减的栈，用于求"下一个更大/更小元素"。

```python
def next_greater_element(nums):
    """
    返回每个元素的下一个更大元素，不存在则为 -1。
    时间复杂度 O(n)，每个元素最多入栈/出栈一次。
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # 存储索引，栈底到栈顶单调递减

    for i in range(n):
        # 当前元素比栈顶大，找到了栈顶的"下一个更大元素"
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

```

### 单调队列

单调队列用于滑动窗口最值问题，队列中元素单调递减（求最大值）或单调递增（求最小值）。

```python
from collections import deque

def sliding_window_max(nums, k):
    """
    返回每个长度为 k 的滑动窗口的最大值。
    时间复杂度 O(n)。
    """
    dq = deque()  # 存储索引，队列中对应的 nums 值单调递减
    result = []

    for i, num in enumerate(nums):
        # 移除队列中小于当前元素的索引（它们不可能是窗口最大值）
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        # 移除不在窗口内的队首元素
        if dq[0] < i - k + 1:
            dq.popleft()

        # 窗口已满
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

```

---

## 哈希表

### Python dict 的底层

Python 3.6+ 的 `dict` 是有序（插入顺序）哈希表：

- 底层使用开放寻址法（Open Addressing）+ 紧凑数组
- 负载因子超过 2/3 时触发扩容（约 2 倍）
- 键必须是可哈希对象（实现了 `__hash__` 和 `__eq__`）
- 查找均摊 O(1)，最坏 O(n)（哈希冲突严重时）

### 哈希冲突处理

| 方式                 | 原理           | 优点           | 缺点              |
| ------------------ | ------------ | ------------ | --------------- |
| 开放寻址（Python dict）  | 冲突时按探测序列寻找空槽 | 缓存友好，无额外内存   | 删除复杂，负载因子高时性能下降 |
| 链地址法（Java HashMap） | 冲突槽位存储链表/红黑树 | 删除简单，负载因子容忍高 | 额外指针开销，缓存不友好    |

### collections.defaultdict

```python
from collections import defaultdict

# 值默认为 list
graph = defaultdict(list)
graph['a'].append('b')  # 不存在 'a' 时自动创建空列表

# 值默认为 int（计数）
counter = defaultdict(int)
for char in "hello":
    counter[char] += 1

# 值默认为 set
adj = defaultdict(set)
adj['a'].add('b')

```

| 参数               | 类型              | 说明                            |
| ---------------- | --------------- | ----------------------------- |
| default\_factory | callable 或 None | 调用无参时产生默认值，None 表示与普通 dict 相同 |

### collections.Counter

```python
from collections import Counter

c = Counter("abracadabra")
print(c.most_common(3))   # [('a', 5), ('b', 2), ('r', 2)]
print(c['a'])             # 5
print(c['z'])             # 0，不存在的键返回 0

# 支持加减运算
c2 = Counter("aab")
print(c + c2)             # 合并计数
print(c - c2)             # 差值（只保留正数）

```

### collections.OrderedDict

Python 3.7+ 普通 `dict` 已保证插入顺序，`OrderedDict` 额外提供 `move_to_end` 方法，常用于实现 LRU 缓存。

```python
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 标记为最近使用
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # 删除最久未使用

```

| 方法                            | 参数              | 说明                                   |
| ----------------------------- | --------------- | ------------------------------------ |
| move\_to\_end(key, last=True) | key, last: bool | last=True 移到末尾，last=False 移到头部       |
| popitem(last=True)            | last: bool      | last=True 删除最后插入的，last=False 删除最早插入的 |

---

## 树

### 二叉树表示

#### 链式表示（面试常用）

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

```

#### 数组表示（堆和完全二叉树）

对于索引从 1 开始的数组：

- 节点 `i` 的左子节点：`2*i`
- 节点 `i` 的右子节点：`2*i + 1`
- 节点 `i` 的父节点：`i // 2`

索引从 0 开始：

- 左子节点：`2*i + 1`
- 右子节点：`2*i + 2`
- 父节点：`(i - 1) // 2`

### 二叉搜索树（BST）

BST 性质：左子树所有值 < 根 < 右子树所有值，中序遍历结果有序。

```python
class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        node = self.root
        while node:
            if val == node.val:
                return True
            node = node.left if val < node.val else node.right
        return False

    def inorder(self):
        """中序遍历返回有序列表"""
        result = []
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(self.root)
        return result

```

### 堆（Heap）

Python `heapq` 维护最小堆，参见[优先队列（heapq）](#%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%EF%BC%88heapq%EF%BC%89)。

手动实现最大堆（用于理解原理）：

```python
class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return root

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self.heap[i] > self.heap[parent]:
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
            parent = (i - 1) // 2

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            largest = i
            left, right = 2 * i + 1, 2 * i + 2
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            if largest == i:
                break
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            i = largest

```

### Trie（前缀树）

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # 是否是某个单词的结尾

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """完整单词查找"""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        """前缀查找"""
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

```

### 并查集（Union-Find）

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始时每个节点是自己的父节点
        self.rank = [0] * n           # 树的高度上界，用于按秩合并
        self.count = n                # 连通分量数

    def find(self, x):
        """路径压缩：递归后将路径上所有节点直接指向根"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """按秩合并"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # 已在同一连通分量
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

```

路径压缩 + 按秩合并后，每次操作的均摊时间复杂度接近 O(1)（严格为 O(α(n))，α 为反阿克曼函数）。

---

## 图

### 邻接矩阵 vs 邻接表

| 特性        | 邻接矩阵  | 邻接表       |
| --------- | ----- | --------- |
| 空间复杂度     | O(V²) | O(V + E)  |
| 判断两点是否相邻  | O(1)  | O(degree) |
| 遍历某节点所有邻居 | O(V)  | O(degree) |
| 适用场景      | 稠密图   | 稀疏图（更常见）  |

```python
# 邻接表（有向带权图）
from collections import defaultdict

graph = defaultdict(list)  # node -> [(neighbor, weight)]
graph[0].append((1, 5))
graph[0].append((2, 3))
graph[1].append((3, 2))

```

### DFS 模板

```python
# 递归 DFS
def dfs_recursive(graph, start):
    visited = set()

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return visited

# 迭代 DFS（使用显式栈，避免递归深度限制）
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

    return visited

```

### BFS 模板

```python
from collections import deque

def bfs(graph, start):
    """
    BFS 层序遍历，同时记录每个节点的最短步数。
    """
    visited = {start}
    queue = deque([(start, 0)])  # (节点, 步数)
    dist = {start: 0}

    while queue:
        node, d = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                dist[neighbor] = d + 1
                queue.append((neighbor, d + 1))

    return dist

```

### Dijkstra 最短路径

适用于非负权有向/无向图。时间复杂度 O((V + E) log V)。

```python
import heapq
from collections import defaultdict

def dijkstra(graph, start, n):
    """
    graph: {node: [(neighbor, weight), ...]}
    返回从 start 到所有节点的最短距离。
    """
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (距离, 节点)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # 已找到更短路径，跳过过时条目
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

```

### 拓扑排序

仅适用于有向无环图（DAG）。

#### Kahn 算法（BFS）

```python
from collections import deque, defaultdict

def topological_sort_kahn(n, edges):
    """
    n: 节点数（0 到 n-1）
    edges: [(u, v), ...] 表示 u -> v
    返回拓扑序列，若存在环则返回空列表。
    """
    in_degree = [0] * n
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # 长度不足说明有环

def topological_sort_dfs(n, edges):
    """
    DFS 后序逆序得到拓扑序。
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * n  # 0: 未访问, 1: 访问中, 2: 已完成
    order = []
    has_cycle = [False]

    def dfs(node):
        if visited[node] == 1:
            has_cycle[0] = True
            return
        if visited[node] == 2:
            return
        visited[node] = 1
        for neighbor in graph[node]:
            dfs(neighbor)
        visited[node] = 2
        order.append(node)

    for i in range(n):
        if visited[i] == 0:
            dfs(i)

    if has_cycle[0]:
        return []
    return order[::-1]

```

---

## 踩坑与注意事项

- `heapq` 只提供最小堆。存储元组 `(priority, item)` 时，若 priority 相同会比较 item，确保 item 可比较或改用 `(priority, counter, item)` 加计数器。
- 递归 DFS 在节点数超过 Python 默认递归限制（1000）时会抛出 `RecursionError`，大图优先用迭代版本或用 `sys.setrecursionlimit` 调整。
- `defaultdict` 访问不存在的键会自动创建，序列化前注意清理，避免意外键出现在 JSON 输出中。
- 并查集的 `find` 带路径压缩时修改了 `parent`，多线程环境下需加锁。
- BST 退化为链表（全升序/全降序插入）时操作变为 O(n)，实际工程中用 AVL 树或红黑树（Python 标准库无内置，可用 `sortedcontainers.SortedList`）。

---

## 最佳实践

**选数据结构前先问"瓶颈在哪"**：写多读少 → 链表/堆；读多写少 → 数组/哈希表；有序范围查询 → 平衡 BST（`sortedcontainers.SortedList`）。用错结构导致的性能问题往往是量级差距，不是常数优化能弥补的。

**Python 内置替代手写结构**：优先用标准库而非手写：

- 队列 → `collections.deque`（O(1) 两端操作）
- 有序容器 → `sortedcontainers.SortedList`
- 优先队列 → `heapq`
- 计数器 → `collections.Counter`
- 双向映射 → `dict` \+ 反转 `dict`

**并查集路径压缩与按秩合并同时开启**：只开路径压缩均摊 O(α(n))，但最坏情况仍可能退化；同时开启按秩合并才能保证严格的逆阿克曼函数复杂度。

**堆元素加懒删除标记替代直接删除**：`heapq` 无法 O(log n) 删除任意元素。常见模式：标记为"已删除"，弹出时跳过：

```python
import heapq

REMOVED = object()

def add_task(heap, entry_finder, task, priority):
    if task in entry_finder:
        entry_finder[task][-1] = REMOVED
    entry = [priority, task]
    entry_finder[task] = entry
    heapq.heappush(heap, entry)

def pop_task(heap, entry_finder):
    while heap:
        priority, task = heapq.heappop(heap)
        if task is not REMOVED:
            del entry_finder[task]
            return priority, task
    raise KeyError("pop from empty heap")

```

**Trie 用 `defaultdict` 递归定义更简洁**：避免手写节点类的样板代码：

```python
from collections import defaultdict

def make_trie():
    return defaultdict(make_trie)

trie = make_trie()
# 插入 "cat"
trie['c']['a']['t']['#'] = True
# 查找前缀 "ca"
node = trie
for ch in "ca":
    if ch not in node:
        break
    node = node[ch]

```

---

## 常见陷阱

### 陷阱：栈/队列用 Python list 导致性能问题

**现象：** 用 `list` 的 `pop(0)` 模拟队列，数据量大时速度极慢。

**原因：** `list.pop(0)` 是 O(n) 操作，需要移动所有后续元素；队列操作应该是 O(1)。

**解决：** 用 `collections.deque`，`appendleft`/`popleft` 均为 O(1)；优先级队列用 `heapq`。

```python
from collections import deque

q = deque()
q.append(1)      # 入队 O(1)
q.popleft()      # 出队 O(1)

# 错误：list 模拟队列
q = []
q.append(1)      # O(1)
q.pop(0)         # O(n)！数据量大时极慢

```

### 陷阱：二叉树递归缺少边界条件导致 RecursionError

**现象：** 递归遍历二叉树时，空节点处报 `RecursionError: maximum recursion depth exceeded`。

**原因：** 未处理 `node is None` 的基础情况，递归函数在空节点处继续调用自身，无限递归。

**解决：** 每个递归函数的第一行必须是空节点检查，立即返回基础值（`None`、`0`、`[]` 等）。

```python
def max_depth(node):
    if node is None:   # 必须放第一行
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

```

### adán：哈希表键为可变对象导致 KeyError

**现象：** 以 `list` 或 `dict` 作为字典键时，创建时正常，取值时报 `TypeError: unhashable type: 'list'`。

**原因：** Python 字典要求键必须是可哈希的（hashable），可变对象（list、dict、set）不可哈希，因为它们的内容可以改变，哈希值不固定。

**解决：** 将 list 键转为 `tuple`，将 dict 键转为 `frozenset` 或 JSON 字符串。

```python
# 错误
d = {[1, 2]: 'value'}  # TypeError

# 正确：转为不可变类型
d = {(1, 2): 'value'}  # tuple 可哈希

```

---

## 参见

[算法思路与模板](https://blog.vercanti.com/suan-fa-si-lu-yu-mo-ban/)