树和图

相关源文件

• 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/206.reverse-linked-list.md
• problems/32.longest-valid-parentheses.md
• problems/371.sum-of-two-integers.md
• problems/42.trapping-rain-water.en.md
• problems/42.trapping-rain-water.md
• problems/92.reverse-linked-list-ii.md
• selected/README.md
• thinkings/basic-data-structure.md
• thinkings/binary-tree-traversal.md
• thinkings/graph.md

本文档提供了对LeetCode仓库中树和图数据结构、算法及其实现的全面概述。它涵盖了与树和图相关的基本概念、遍历算法以及常见的解题模式。

有关一般基本数据结构的信息，请参阅基本数据结构。有关Trie等更具体的树实现，请参阅Trie（前缀树），有关并查集数据结构，请参阅并查集。

树数据结构

树是分层数据结构，具有根值和子节点组成的子树，表示为一组链接节点。它们因插入、删除和查找的高效操作而被广泛使用。

二叉树

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

来源：thinkings/basic-data-structure.md247-289 thinkings/binary-tree-traversal.md1-9

二叉搜索树

二叉搜索树（BST）是一种特殊的二叉树，其中

• 左子节点包含小于父节点的值
• 右子节点包含大于父节点的值
• 左子树和右子树也都是二叉搜索树
• 不允许重复值

这种有序性使得二叉搜索树在查找操作上非常高效。

来源：thinkings/basic-data-structure.md330-353

平衡二叉树

平衡二叉树是旨在维持对数高度的二叉树，以确保高效的操作。最常见的类型包括

1. AVL树 - 自平衡二叉搜索树，其中两棵子树的高度之差最多为1
2. 红黑树 - 自平衡二叉搜索树，对操作有良好的最坏情况保证

来源：thinkings/basic-data-structure.md356-382

树的遍历算法

树的遍历是访问树数据结构中每个节点恰好一次的过程。根据问题的具体要求，会使用不同的遍历算法。

深度优先搜索 (DFS)

深度优先搜索（DFS）在回溯之前尽可能深入地遍历每个分支。二叉树有三种主要的DFS遍历方式：

前序遍历（根-左-右）

访问顺序：1, 2, 4, 5, 3, 6, 7

中序遍历（左-根-右）

访问顺序：4, 2, 5, 1, 6, 3, 7

后序遍历（左-右-根）

访问顺序：4, 5, 2, 6, 7, 3, 1

来源：thinkings/binary-tree-traversal.md11-87

广度优先搜索 (BFS)

广度优先搜索（BFS）在移动到下一深度级别的节点之前，会访问当前深度下的所有邻居节点。当应用于树时，它也称为层序遍历。

访问顺序：1, 2, 3, 4, 5, 6, 7

来源：thinkings/binary-tree-traversal.md89-106 problems/102.binary-tree-level-order-traversal.md40-50

高级遍历技术

双色标记法

该技术在遍历过程中使用颜色来标记节点

• 白色节点是未访问的
• 灰色节点已被访问

这种方法允许以迭代方式实现递归遍历模式。

来源：thinkings/binary-tree-traversal.md112-153

莫里斯遍历

莫里斯遍历允许以常数空间复杂度（O(1)）遍历二叉树，而无需使用递归或堆栈。

来源：thinkings/binary-tree-traversal.md156-201

图数据结构

图由顶点（节点）和连接这些顶点的边组成。它们用于表示网络和实体之间的关系。

图的表示方法

邻接矩阵

邻接矩阵是一个二维数组，其中 matrix[i][j] 表示从顶点 i 到顶点 j 的边。对于带权图，该值可以表示边的权重。

邻接表

邻接表使用列表的数组或哈希表，其中每个列表表示特定顶点的邻居。

来源：thinkings/graph.md58-157 thinkings/basic-data-structure.md410-411

图遍历算法

深度优先搜索 (DFS)

DFS 通过沿着每条分支尽可能深入地探索图，然后在回溯。

广度优先搜索 (BFS)

BFS 按层级探索图，在移动到其邻居之前访问一个节点的所有邻居。

来源：thinkings/graph.md158-185

最短路径算法

Dijkstra 算法

Dijkstra 算法在具有非负边权的有权图中找到源节点到所有其他节点的最短路径。

来源：thinkings/graph.md208-411

Floyd-Warshall 算法

Floyd-Warshall 算法在有负边权（但无负环）的有权图中查找所有节点对之间的最短路径。

来源：thinkings/graph.md418-626

常见的树和图问题

二叉树问题

问题类型	描述	示例问题
树遍历	访问树中所有节点的不同方法	二叉树层序遍历
路径问题	查找树中满足特定条件的路径	路径总和 II
树的属性	验证或计算树的属性	二叉树的最大深度
树的构建	根据遍历结果构建树	请参阅构建二叉树

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

图问题

问题类型	描述	示例问题
最短路径	查找节点之间的最短路径	网络延迟时间
连接性	确定节点是否连通	验证二叉搜索树
环检测	查找图中的环	最长有效括号
图遍历	访问图节点的不同方法	二叉树的最大深度

来源：problems/32.longest-valid-parentheses.md thinkings/graph.md

实现模式

二叉树节点结构

代码库中二叉树的标准表示

来源： problems/102.binary-tree-level-order-traversal.md69-77

图构建技术

数组邻接矩阵

哈希表邻接列表

来源： thinkings/graph.md120-136

常用树算法实现

DFS递归实现

BFS迭代实现

来源： problems/102.binary-tree-level-order-traversal.md75-102 thinkings/binary-tree-traversal.md27-44

高级技巧

树的翻转

反转链表（或树中的路径）是一个常见的操作

来源： problems/206.reverse-linked-list.md76-90

接雨水问题

“接雨水”之类的问题使用可以被视为图遍历的技术

来源： problems/42.trapping-rain-water.md157-213