wehub-skill-sync
684 lines
14 KiB
Markdown
684 lines
14 KiB
Markdown
# 树与图参考
|
||
|
||
## 二叉树
|
||
|
||
### 核心概念
|
||
|
||
**二叉树**是一种层次化数据结构，每个节点最多有两个子节点（左子节点与右子节点）。
|
||
|
||
**关键属性**：
|
||
- 每个节点最多有 2 个子节点
|
||
- 根节点没有父节点
|
||
- 叶节点没有子节点
|
||
- 高度：从根节点到叶节点的最长路径
|
||
- 深度：从根节点到某节点的距离
|
||
|
||
**二叉树类型**：
|
||
- **满二叉树**：每个节点有 0 或 2 个子节点
|
||
- **完全二叉树**：除最后一层外，所有层都被填满，且最后一层从左向右填充
|
||
- **完美二叉树**：所有内部节点都有 2 个子节点，所有叶节点在同一层
|
||
- **平衡二叉树**：左右子树的高度差 ≤ 1
|
||
|
||
### 节点结构
|
||
|
||
**Python**：
|
||
```python
|
||
class TreeNode:
|
||
def __init__(self, val=0, left=None, right=None):
|
||
self.val = val
|
||
self.left = left
|
||
self.right = right
|
||
```
|
||
|
||
**JavaScript**：
|
||
```javascript
|
||
class TreeNode {
|
||
constructor(val = 0, left = null, right = null) {
|
||
this.val = val;
|
||
this.left = left;
|
||
this.right = right;
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 树的遍历
|
||
|
||
### 1. 深度优先搜索（DFS）
|
||
|
||
#### 中序遍历（左 → 根 → 右）
|
||
**用途**：BST 可得到有序序列
|
||
```python
|
||
def inorder(root):
|
||
result = []
|
||
|
||
def traverse(node):
|
||
if not node:
|
||
return
|
||
traverse(node.left)
|
||
result.append(node.val)
|
||
traverse(node.right)
|
||
|
||
traverse(root)
|
||
return result
|
||
```
|
||
|
||
#### 前序遍历（根 → 左 → 右）
|
||
**用途**：复制树、前缀表达式
|
||
```python
|
||
def preorder(root):
|
||
result = []
|
||
|
||
def traverse(node):
|
||
if not node:
|
||
return
|
||
result.append(node.val)
|
||
traverse(node.left)
|
||
traverse(node.right)
|
||
|
||
traverse(root)
|
||
return result
|
||
```
|
||
|
||
#### 后序遍历（左 → 右 → 根）
|
||
**用途**：删除树、后缀表达式
|
||
```python
|
||
def postorder(root):
|
||
result = []
|
||
|
||
def traverse(node):
|
||
if not node:
|
||
return
|
||
traverse(node.left)
|
||
traverse(node.right)
|
||
result.append(node.val)
|
||
|
||
traverse(root)
|
||
return result
|
||
```
|
||
|
||
### 2. 广度优先搜索（BFS）
|
||
|
||
**用途**：层序遍历、无权重树中的最短路径
|
||
```python
|
||
from collections import deque
|
||
|
||
def level_order(root):
|
||
if not root:
|
||
return []
|
||
|
||
result = []
|
||
queue = deque([root])
|
||
|
||
while queue:
|
||
level_size = len(queue)
|
||
current_level = []
|
||
|
||
for _ in range(level_size):
|
||
node = queue.popleft()
|
||
current_level.append(node.val)
|
||
|
||
if node.left:
|
||
queue.append(node.left)
|
||
if node.right:
|
||
queue.append(node.right)
|
||
|
||
result.append(current_level)
|
||
|
||
return result
|
||
```
|
||
|
||
**时间**：O(n)，**空间**：O(w)，其中 w 为最大宽度
|
||
|
||
---
|
||
|
||
## 二叉搜索树（BST）
|
||
|
||
### 属性
|
||
- 左子树的值 < 节点值
|
||
- 右子树的值 > 节点值
|
||
- 左右子树也都是 BST
|
||
- 中序遍历得到有序序列
|
||
|
||
### 常见操作
|
||
|
||
#### 查找
|
||
```python
|
||
def search_bst(root, val):
|
||
if not root or root.val == val:
|
||
return root
|
||
|
||
if val < root.val:
|
||
return search_bst(root.left, val)
|
||
return search_bst(root.right, val)
|
||
```
|
||
**时间**：O(h)，其中 h 为高度（平衡时 O(log n)，最坏 O(n)）
|
||
|
||
#### 插入
|
||
```python
|
||
def insert_bst(root, val):
|
||
if not root:
|
||
return TreeNode(val)
|
||
|
||
if val < root.val:
|
||
root.left = insert_bst(root.left, val)
|
||
else:
|
||
root.right = insert_bst(root.right, val)
|
||
|
||
return root
|
||
```
|
||
|
||
#### 删除
|
||
```python
|
||
def delete_bst(root, val):
|
||
if not root:
|
||
return None
|
||
|
||
if val < root.val:
|
||
root.left = delete_bst(root.left, val)
|
||
elif val > root.val:
|
||
root.right = delete_bst(root.right, val)
|
||
else:
|
||
# 找到待删除节点
|
||
# 情况 1：无子节点
|
||
if not root.left and not root.right:
|
||
return None
|
||
|
||
# 情况 2：只有一个子节点
|
||
if not root.left:
|
||
return root.right
|
||
if not root.right:
|
||
return root.left
|
||
|
||
# 情况 3：有两个子节点
|
||
# 寻找中序后继（右子树中的最小值）
|
||
min_node = find_min(root.right)
|
||
root.val = min_node.val
|
||
root.right = delete_bst(root.right, min_node.val)
|
||
|
||
return root
|
||
|
||
def find_min(node):
|
||
while node.left:
|
||
node = node.left
|
||
return node
|
||
```
|
||
|
||
---
|
||
|
||
## 常见树算法
|
||
|
||
### 1. 树的高度/深度
|
||
```python
|
||
def max_depth(root):
|
||
if not root:
|
||
return 0
|
||
return 1 + max(max_depth(root.left), max_depth(root.right))
|
||
```
|
||
|
||
### 2. 平衡树检查
|
||
```python
|
||
def is_balanced(root):
|
||
def height(node):
|
||
if not node:
|
||
return 0
|
||
|
||
left_height = height(node.left)
|
||
if left_height == -1:
|
||
return -1
|
||
|
||
right_height = height(node.right)
|
||
if right_height == -1:
|
||
return -1
|
||
|
||
if abs(left_height - right_height) > 1:
|
||
return -1
|
||
|
||
return 1 + max(left_height, right_height)
|
||
|
||
return height(root) != -1
|
||
```
|
||
|
||
### 3. 最近公共祖先（BST）
|
||
```python
|
||
def lowest_common_ancestor_bst(root, p, q):
|
||
if p.val < root.val and q.val < root.val:
|
||
return lowest_common_ancestor_bst(root.left, p, q)
|
||
if p.val > root.val and q.val > root.val:
|
||
return lowest_common_ancestor_bst(root.right, p, q)
|
||
return root
|
||
```
|
||
|
||
### 4. 二叉树的直径
|
||
```python
|
||
def diameter_of_binary_tree(root):
|
||
diameter = 0
|
||
|
||
def height(node):
|
||
nonlocal diameter
|
||
if not node:
|
||
return 0
|
||
|
||
left = height(node.left)
|
||
right = height(node.right)
|
||
|
||
diameter = max(diameter, left + right)
|
||
return 1 + max(left, right)
|
||
|
||
height(root)
|
||
return diameter
|
||
```
|
||
|
||
### 5. 序列化与反序列化
|
||
```python
|
||
def serialize(root):
|
||
"""将树编码为字符串。"""
|
||
def helper(node):
|
||
if not node:
|
||
return 'null,'
|
||
return str(node.val) + ',' + helper(node.left) + helper(node.right)
|
||
|
||
return helper(root)
|
||
|
||
def deserialize(data):
|
||
"""将字符串解码为树。"""
|
||
def helper(nodes):
|
||
val = next(nodes)
|
||
if val == 'null':
|
||
return None
|
||
node = TreeNode(int(val))
|
||
node.left = helper(nodes)
|
||
node.right = helper(nodes)
|
||
return node
|
||
|
||
return helper(iter(data.split(',')))
|
||
```
|
||
|
||
---
|
||
|
||
## 图
|
||
|
||
### 核心概念
|
||
|
||
**图**是由边连接的节点（顶点）集合。
|
||
|
||
**类型**：
|
||
- **有向图**与**无向图**：边是否有方向
|
||
- **有权图**与**无权图**：边是否带有权重
|
||
- **有环图**与**无环图**：是否包含环
|
||
- **连通图**与**非连通图**：所有节点之间是否存在路径
|
||
|
||
### 表示方法
|
||
|
||
#### 1. 邻接表（最常用）
|
||
```python
|
||
# 无向图
|
||
graph = {
|
||
'A': ['B', 'C'],
|
||
'B': ['A', 'D', 'E'],
|
||
'C': ['A', 'F'],
|
||
'D': ['B'],
|
||
'E': ['B', 'F'],
|
||
'F': ['C', 'E']
|
||
}
|
||
|
||
# 或使用 defaultdict
|
||
from collections import defaultdict
|
||
graph = defaultdict(list)
|
||
graph['A'].append('B')
|
||
graph['B'].append('A')
|
||
```
|
||
|
||
**空间**：O(V + E)
|
||
|
||
#### 2. 邻接矩阵
|
||
```python
|
||
# graph[i][j] = 1 表示存在从 i 到 j 的边
|
||
n = 5 # 顶点数
|
||
graph = [[0] * n for _ in range(n)]
|
||
graph[0][1] = 1 # 从 0 到 1 的边
|
||
graph[1][0] = 1 # 从 1 到 0 的边（无向）
|
||
```
|
||
|
||
**空间**：O(V²)
|
||
|
||
---
|
||
|
||
## 图的遍历
|
||
|
||
### 1. 深度优先搜索（DFS）
|
||
|
||
**递归**：
|
||
```python
|
||
def dfs(graph, start, visited=None):
|
||
if visited is None:
|
||
visited = set()
|
||
|
||
visited.add(start)
|
||
print(start)
|
||
|
||
for neighbor in graph[start]:
|
||
if neighbor not in visited:
|
||
dfs(graph, neighbor, visited)
|
||
|
||
return visited
|
||
```
|
||
|
||
**迭代**（使用栈）：
|
||
```python
|
||
def dfs_iterative(graph, start):
|
||
visited = set()
|
||
stack = [start]
|
||
|
||
while stack:
|
||
node = stack.pop()
|
||
|
||
if node not in visited:
|
||
visited.add(node)
|
||
print(node)
|
||
|
||
for neighbor in graph[node]:
|
||
if neighbor not in visited:
|
||
stack.append(neighbor)
|
||
|
||
return visited
|
||
```
|
||
|
||
**时间**：O(V + E)，**空间**：O(V)
|
||
|
||
### 2. 广度优先搜索（BFS）
|
||
|
||
```python
|
||
from collections import deque
|
||
|
||
def bfs(graph, start):
|
||
visited = set([start])
|
||
queue = deque([start])
|
||
|
||
while queue:
|
||
node = queue.popleft()
|
||
print(node)
|
||
|
||
for neighbor in graph[node]:
|
||
if neighbor not in visited:
|
||
visited.add(neighbor)
|
||
queue.append(neighbor)
|
||
|
||
return visited
|
||
```
|
||
|
||
**时间**：O(V + E)，**空间**：O(V)
|
||
|
||
---
|
||
|
||
## 常见图算法
|
||
|
||
### 1. 环检测（无向图）
|
||
```python
|
||
def has_cycle(graph):
|
||
visited = set()
|
||
|
||
def dfs(node, parent):
|
||
visited.add(node)
|
||
|
||
for neighbor in graph[node]:
|
||
if neighbor not in visited:
|
||
if dfs(neighbor, node):
|
||
return True
|
||
elif neighbor != parent:
|
||
return True # 发现环
|
||
|
||
return False
|
||
|
||
for node in graph:
|
||
if node not in visited:
|
||
if dfs(node, None):
|
||
return True
|
||
|
||
return False
|
||
```
|
||
|
||
### 2. 环检测（有向图）
|
||
```python
|
||
def has_cycle_directed(graph):
|
||
WHITE, GRAY, BLACK = 0, 1, 2
|
||
color = {node: WHITE for node in graph}
|
||
|
||
def dfs(node):
|
||
color[node] = GRAY
|
||
|
||
for neighbor in graph[node]:
|
||
if color[neighbor] == GRAY:
|
||
return True # 发现回边
|
||
if color[neighbor] == WHITE and dfs(neighbor):
|
||
return True
|
||
|
||
color[node] = BLACK
|
||
return False
|
||
|
||
for node in graph:
|
||
if color[node] == WHITE:
|
||
if dfs(node):
|
||
return True
|
||
|
||
return False
|
||
```
|
||
|
||
### 3. 拓扑排序（DAG）
|
||
```python
|
||
def topological_sort(graph):
|
||
visited = set()
|
||
stack = []
|
||
|
||
def dfs(node):
|
||
visited.add(node)
|
||
|
||
for neighbor in graph[node]:
|
||
if neighbor not in visited:
|
||
dfs(neighbor)
|
||
|
||
stack.append(node)
|
||
|
||
for node in graph:
|
||
if node not in visited:
|
||
dfs(node)
|
||
|
||
return stack[::-1] # 反转
|
||
```
|
||
|
||
**时间**：O(V + E)
|
||
|
||
### 4. 最短路径（无权图 - BFS）
|
||
```python
|
||
from collections import deque
|
||
|
||
def shortest_path_bfs(graph, start, end):
|
||
queue = deque([(start, [start])])
|
||
visited = set([start])
|
||
|
||
while queue:
|
||
node, path = queue.popleft()
|
||
|
||
if node == end:
|
||
return path
|
||
|
||
for neighbor in graph[node]:
|
||
if neighbor not in visited:
|
||
visited.add(neighbor)
|
||
queue.append((neighbor, path + [neighbor]))
|
||
|
||
return None # 未找到路径
|
||
```
|
||
|
||
### 5. Dijkstra 算法（有权图）
|
||
```python
|
||
import heapq
|
||
|
||
def dijkstra(graph, start):
|
||
"""找到从起点到所有节点的最短路径。"""
|
||
distances = {node: float('inf') for node in graph}
|
||
distances[start] = 0
|
||
pq = [(0, start)] # (距离, 节点)
|
||
|
||
while pq:
|
||
current_dist, current_node = heapq.heappop(pq)
|
||
|
||
if current_dist > distances[current_node]:
|
||
continue
|
||
|
||
for neighbor, weight in graph[current_node]:
|
||
distance = current_dist + weight
|
||
|
||
if distance < distances[neighbor]:
|
||
distances[neighbor] = distance
|
||
heapq.heappush(pq, (distance, neighbor))
|
||
|
||
return distances
|
||
```
|
||
|
||
**时间**：O((V + E) log V)（使用最小堆）
|
||
|
||
### 6. 并查集（不相交集合）
|
||
```python
|
||
class UnionFind:
|
||
def __init__(self, n):
|
||
self.parent = list(range(n))
|
||
self.rank = [0] * 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):
|
||
root_x = self.find(x)
|
||
root_y = self.find(y)
|
||
|
||
if root_x == root_y:
|
||
return False
|
||
|
||
# 按秩合并
|
||
if self.rank[root_x] < self.rank[root_y]:
|
||
self.parent[root_x] = root_y
|
||
elif self.rank[root_x] > self.rank[root_y]:
|
||
self.parent[root_y] = root_x
|
||
else:
|
||
self.parent[root_y] = root_x
|
||
self.rank[root_x] += 1
|
||
|
||
return True
|
||
```
|
||
|
||
**用途**：环检测、Kruskal 最小生成树、连通分量
|
||
|
||
---
|
||
|
||
## 常见图问题
|
||
|
||
### 1. 岛屿数量
|
||
```python
|
||
def num_islands(grid):
|
||
if not grid:
|
||
return 0
|
||
|
||
count = 0
|
||
rows, cols = len(grid), len(grid[0])
|
||
|
||
def dfs(r, c):
|
||
if (r < 0 or r >= rows or c < 0 or c >= cols or
|
||
grid[r][c] == '0'):
|
||
return
|
||
|
||
grid[r][c] = '0' # 标记为已访问
|
||
dfs(r + 1, c)
|
||
dfs(r - 1, c)
|
||
dfs(r, c + 1)
|
||
dfs(r, c - 1)
|
||
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if grid[r][c] == '1':
|
||
count += 1
|
||
dfs(r, c)
|
||
|
||
return count
|
||
```
|
||
|
||
### 2. 课程表（环检测）
|
||
```python
|
||
def can_finish(num_courses, prerequisites):
|
||
graph = defaultdict(list)
|
||
for course, prereq in prerequisites:
|
||
graph[course].append(prereq)
|
||
|
||
WHITE, GRAY, BLACK = 0, 1, 2
|
||
color = [WHITE] * num_courses
|
||
|
||
def has_cycle(course):
|
||
color[course] = GRAY
|
||
|
||
for prereq in graph[course]:
|
||
if color[prereq] == GRAY:
|
||
return True
|
||
if color[prereq] == WHITE and has_cycle(prereq):
|
||
return True
|
||
|
||
color[course] = BLACK
|
||
return False
|
||
|
||
for course in range(num_courses):
|
||
if color[course] == WHITE:
|
||
if has_cycle(course):
|
||
return False
|
||
|
||
return True
|
||
```
|
||
|
||
### 3. 克隆图
|
||
```python
|
||
def clone_graph(node):
|
||
if not node:
|
||
return None
|
||
|
||
clones = {}
|
||
|
||
def dfs(node):
|
||
if node in clones:
|
||
return clones[node]
|
||
|
||
clone = Node(node.val)
|
||
clones[node] = clone
|
||
|
||
for neighbor in node.neighbors:
|
||
clone.neighbors.append(dfs(neighbor))
|
||
|
||
return clone
|
||
|
||
return dfs(node)
|
||
```
|
||
|
||
---
|
||
|
||
## 何时使用何种方法
|
||
|
||
**树的遍历**：
|
||
- **DFS（中序）**：BST → 有序序列
|
||
- **DFS（前序）**：复制树、前缀表示法
|
||
- **DFS（后序）**：删除树、后缀表示法
|
||
- **BFS**：层序遍历、最短路径
|
||
|
||
**图的遍历**：
|
||
- **DFS**：环检测、拓扑排序、连通分量
|
||
- **BFS**：最短路径（无权图）、按层探索
|
||
|
||
**最短路径**：
|
||
- **BFS**：无权图
|
||
- **Dijkstra**：有权图（非负权重）
|
||
- **Bellman-Ford**：有权图（可含负权重）
|
||
- **Floyd-Warshall**：所有点对最短路径
|
||
|
||
**树/图表示选择**：
|
||
- **邻接表**：稀疏图（E << V²）
|
||
- **邻接矩阵**：稠密图、快速边查询
|