在 LeetCode 的算法题中，树与图是两类不可或缺的重要数据结构。无论是探索二叉树的深度，还是解决复杂的最短路径问题，树与图的应用无处不在。它们不仅是计算机科学的基石，也是提升算法能力的关键。
1.理论
1.1.树与图的基础概念
1.1.1.树 (Tree)
是一种特殊的图，是无环、连通的图，常见类型有二叉树、二叉搜索树 (BST)、完全二叉树等。
特点：节点之间有父子关系；每个节点最多只有一个父节点，根节点没有父节点；边的数量 = 节点数量 - 1。
1.1.2.图 (Graph)
图是由节点 (Vertices) 和边 (Edges) 组成的结构，可以是有向图或无向图，带权图或无权图。
特点：可包含环 (Cycle)；节点可以没有父子关系；常用的表示方法有邻接矩阵和邻接表。
1.2.常见问题分类
1.2.1.树的经典问题
二叉树遍历
- 前序遍历 (Preorder): 根 - 左 - 右
- 中序遍历 (Inorder): 左 - 根 - 右
- 后序遍历 (Postorder): 左 - 右 - 根
- 层序遍历 (Level Order Traversal): 一层一层从上到下遍历。
树的构建
- 根据前序和中序遍历序列构建二叉树。
- 根据中序和后序遍历序列构建二叉树。
树的属性
- 最大深度、最小深度。
- 是否平衡二叉树。
- 二叉搜索树的验证。
树的修改与路径
- 最近公共祖先 (LCA)。
- 求根到叶子的路径和。
- 二叉树的直径问题。
1.2.2.图的经典问题
图的遍历：深度优先搜索 (DFS)和广度优先搜索 (BFS)
最短路径问题
连通性问题
- 判断连通分量的个数。
- 判断图是否是二分图。
拓扑排序
- Kahn 算法。
- 基于 DFS 的拓扑排序。
最小生成树 (MST)
网络流问题：最大流：Edmonds-Karp 算法，Ford-Fulkerson 算法。
1.3.关键算法模板
1.3.1.DFS 模板
def dfs(node, visited):if node in visited:returnvisited.add(node)for neighbor in graph[node]:dfs(neighbor, visited)
1.3.2.BFS 模板
from collections import dequedef bfs(start):queue = deque([start])visited = set()visited.add(start)while queue:node = queue.popleft()for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)
1.3.3.二叉树递归遍历模板
def inorder_traversal(root):if not root:return []return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
2.真题
2.1.树相关
2.1.1.简单(Easy)
【Leetcode 94】二叉树的中序遍历
给定二叉树的 ，返回其节点值的中序遍历。
如果以空间复杂度优先：Morris 遍历是最优解，空间复杂度仅为 O(1)。
如果以易读性优先：递归解法更清晰简单，适合初学者。
如果需要平衡效率和易读性：迭代解法是最常用的方法。
递归解法
# 中序遍历的顺序是：左子树 → 根节点 → 右子树。def inorderTraversal(root):def dfs(node):if not node:return [] #如果当前节点是 None（即递归到达叶子节点的子节点），返回空列表return dfs(node.left)+[node.val]+dfs(node.right) #拼接结果return dfs(root) #时间复杂度：O(n);空间复杂度：O(n)（递归调用栈）【Leetcode 104】二叉树的最大深度
2.1.2.中等(Medium)
【Leetcode 94】二叉树的中序遍历
2.2.图相关
2.2.2.中等(Medium)
【Leetcode 200】岛屿的数量
【Leetcode236】课程表
【Leetcode236】网络延迟时间
参考文献
【1】 Trees vs. Graphs - Open4Tech
