树和图问题

相关源文件

• assets/problems/121.best-time-to-buy-and-sell-stock.jpg
• problems/102.binary-tree-level-order-traversal.md
• problems/104.maximum-depth-of-binary-tree.md
• problems/113.path-sum-ii.md
• problems/121.best-time-to-buy-and-sell-stock.md
• problems/122.best-time-to-buy-and-sell-stock-ii.md
• problems/371.sum-of-two-integers.md
• problems/94.binary-tree-inorder-traversal.md
• problems/98.validate-binary-search-tree.md

本页面记录了 LeetCode 仓库中常见的树和图问题模式，对数据结构、遍历方法和针对这些结构的特定解题策略进行了系统性概述。它为理解代码库中如何处理和解决树与图问题提供了参考。

有关更基础数据结构的信息，请参阅 基础数据结构。有关如字典树之类的专用树结构，请参阅 字典树（前缀树），有关并查集实现，请参阅 并查集。

树数据结构

此仓库中的树通常使用具有以下结构的 TreeNode 类表示

标准定义出现在大多数树问题文件中

来源：problems/94.binary-tree-inorder-traversal.md147-155 problems/98.validate-binary-search-tree.md82-88

树的遍历技术

深度优先搜索 (DFS)

深度优先搜索（DFS）通过沿每个分支尽可能深地探索，然后在回溯，来遍历树。二叉树有三种标准的 DFS 遍历顺序：

中序遍历实现

该仓库提供了中序遍历的迭代实现。

该算法

1. 使用栈模拟递归
2. 遍历到最左节点
3. 处理完当前节点的左子树后处理该节点
4. 移动到右子树

来源：problems/94.binary-tree-inorder-traversal.md77-90

广度优先搜索（BFS）/层序遍历

BFS 从上到下逐层遍历树，通常使用队列实现。

该仓库在 problems/102.binary-tree-level-order-traversal.md75-103 中实现了层序遍历，使用了带空标记的队列来分隔层级。

来源：problems/102.binary-tree-level-order-traversal.md75-103

图的表示方法

该仓库使用两种主要的图表示法

常见的树与图问题模式

二叉搜索树操作

二叉搜索树（BST）遵循这样的属性：左子树中的所有节点值小于该节点，右子树中的所有节点值大于该节点。

该仓库实现了两种 BST 验证方法：

1. 使用中序遍历检查值是否升序排列

2. 使用递归范围检查

来源：problems/98.validate-binary-search-tree.md51-66 problems/98.validate-binary-search-tree.md93-121 problems/98.validate-binary-search-tree.md341-353

路径查找问题

根节点到叶节点路径总和

pathSum 函数查找从根到叶子的所有路径，其中节点值之和等于目标值。

实现使用了回溯法，并用一个临时列表来跟踪当前路径。

来源：problems/113.path-sum-ii.md42-48 problems/113.path-sum-ii.md81-91

树的属性

最大深度（高度）

查找二叉树的最大深度是一个经典的树问题。

该仓库以两种方式实现此问题：

1. 递归（简洁优雅）

2. 迭代使用带有层级跟踪的 BFS

来源：problems/104.maximum-depth-of-binary-tree.md42-55 problems/104.maximum-depth-of-binary-tree.md46-52 problems/104.maximum-depth-of-binary-tree.md90-111

高级图算法

图的遍历技术

图的遍历技术在操作更通用的图结构时，与树的遍历类似。

岛屿问题

岛屿问题涉及识别基于网格的图中的连通分量，通常使用 DFS 或 BFS。

并查集（Disjoint Set）

并查集是一种用于维护和合并不相交集合的有效数据结构，常用于图的连通性问题。

有关并查集的详细实现，请参阅 并查集。

最短路径算法

对于加权图，有专门的算法来查找最优路径。

总结

树与图问题构成了此仓库中算法问题的重要组成部分。解决方案采用了标准的数据结构和遍历技术，并根据具体问题要求进行定制。

关键技术包括：

• 用于探索的 DFS 和 BFS 遍历
• 用于路径查找的回溯
• 递归和迭代方法
• 用于连通性的并查集等专用结构

理解这些模式有助于高效地解决各种树和图挑战。

来源：problems/94.binary-tree-inorder-traversal.md problems/98.validate-binary-search-tree.md problems/102.binary-tree-level-order-traversal.md problems/104.maximum-depth-of-binary-tree.md problems/113.path-sum-ii.md