Appearance
高频树图
二叉树锯齿形层序遍历
二叉树锯齿形层序遍历
它本质还是 BFS 层序遍历，队列出队顺序不变，仍然是一层一层从左到右取节点。 区别只在于：保存当前层结果时，根据方向决定插到尾部还是头部。
比如：
3
/ \
9 20
/ \
15 7普通层序是：
[[3], [9, 20], [15, 7]]锯齿形层序是：
[[3], [20, 9], [15, 7]]
核心思路
用 Queue<TreeNode> 做 BFS。 每次先记录当前层节点数量 count = queue.Count，这样就能保证只处理当前这一层。 用 LinkedList<int> 存当前层结果：
- 从左到右：
AddLast(node.val) - 从右到左：
AddFirst(node.val) - 每处理完一层：
leftToRight = !leftToRight
C# 代码
c
using System.Collections.Generic; // 引入 Queue、List、LinkedList 等集合类型
public class TreeNode // 定义二叉树节点类
{ // 节点类开始
public int val; // 当前节点的值
public TreeNode left; // 当前节点的左子节点
public TreeNode right; // 当前节点的右子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.left = left; // 初始化左子节点
this.right = right; // 初始化右子节点
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) // 定义锯齿形层序遍历方法
{ // 方法开始
List<IList<int>> result = new List<IList<int>>(); // 创建最终结果列表
if (root == null) // 如果根节点为空
{ // 空树判断开始
return result; // 空树直接返回空结果
} // 空树判断结束
Queue<TreeNode> queue = new Queue<TreeNode>(); // 创建队列用于 BFS 层序遍历
queue.Enqueue(root); // 把根节点加入队列
bool leftToRight = true; // 记录当前层是否从左到右保存结果
while (queue.Count > 0) // 只要队列不为空就继续遍历
{ // 外层循环开始
int count = queue.Count; // 固定当前层的节点数量
LinkedList<int> level = new LinkedList<int>(); // 创建当前层结果链表
for (int i = 0; i < count; i++) // 遍历当前层的所有节点
{ // for 循环开始
TreeNode node = queue.Dequeue(); // 从队列中取出当前节点
if (leftToRight) // 如果当前层要求从左到右
{ // 方向判断开始
level.AddLast(node.val); // 把节点值加入当前层尾部
} // 方向判断结束
else // 如果当前层要求从右到左
{ // 反方向判断开始
level.AddFirst(node.val); // 把节点值加入当前层头部
} // 反方向判断结束
if (node.left != null) // 如果左子节点不为空
{ // 左子节点判断开始
queue.Enqueue(node.left); // 左子节点入队
} // 左子节点判断结束
if (node.right != null) // 如果右子节点不为空
{ // 右子节点判断开始
queue.Enqueue(node.right); // 右子节点入队
} // 右子节点判断结束
} // for 循环结束
result.Add(new List<int>(level)); // 把当前层结果加入最终答案
leftToRight = !leftToRight; // 当前层结束后切换下一层方向
} // 外层循环结束
return result; // 返回最终锯齿形层序遍历结果
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只遍历一次。 空间复杂度：O(n)，队列和结果列表最多存储所有节点。
面试记忆
CAUTION
队列负责“按层取节点”，方向变量负责“这一层怎么存结果”。 也就是：BFS 不变，结果插入方向变化。
从前序和中序构造二叉树
从前序和中序构造二叉树
这题的核心口诀是：前序定根，中序分左右。
前序遍历顺序是：
根 -> 左子树 -> 右子树中序遍历顺序是：
左子树 -> 根 -> 右子树所以前序数组的第一个值，一定是当前子树的根。 然后去中序数组里找到这个根，根左边就是左子树，根右边就是右子树。
例子
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]前序第一个是 3，所以 3 是根节点。
在中序里：
[9, 3, 15, 20, 7]3 左边是 [9]，所以左子树是 9。 3 右边是 [15, 20, 7]，所以右子树继续递归构造。
C# 代码
c
using System.Collections.Generic; // 引入 Dictionary 集合类型
public class TreeNode // 定义二叉树节点类
{ // 节点类开始
public int val; // 当前节点的值
public TreeNode left; // 当前节点的左子节点
public TreeNode right; // 当前节点的右子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) // 定义构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.left = left; // 初始化左子节点
this.right = right; // 初始化右子节点
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
private int preIndex; // 记录当前用到了前序数组的哪个位置
private int[] preorderArray; // 保存前序数组，方便递归函数使用
private Dictionary<int, int> inorderIndexMap; // 保存中序数组中每个值对应的下标
public TreeNode BuildTree(int[] preorder, int[] inorder) // 根据前序和中序构造二叉树
{ // 方法开始
preIndex = 0; // 前序数组从第 0 个位置开始取根节点
preorderArray = preorder; // 保存前序数组引用
inorderIndexMap = new Dictionary<int, int>(); // 创建哈希表用于快速定位根节点
for (int i = 0; i < inorder.Length; i++) // 遍历中序数组
{ // for 循环开始
inorderIndexMap[inorder[i]] = i; // 记录每个节点值在中序数组中的下标
} // for 循环结束
return Build(0, inorder.Length - 1); // 从整个中序范围开始递归构造
} // 方法结束
private TreeNode Build(int inLeft, int inRight) // 构造中序区间 [inLeft, inRight] 对应的子树
{ // 递归函数开始
if (inLeft > inRight) // 如果左边界超过右边界，说明当前子树为空
{ // 空区间判断开始
return null; // 返回空节点
} // 空区间判断结束
int rootValue = preorderArray[preIndex]; // 前序当前位置就是当前子树根节点的值
preIndex++; // 前序指针后移，准备给下一棵子树取根
TreeNode root = new TreeNode(rootValue); // 创建当前根节点
int rootIndex = inorderIndexMap[rootValue]; // 找到根节点在中序数组中的位置
root.left = Build(inLeft, rootIndex - 1); // 递归构造左子树
root.right = Build(rootIndex + 1, inRight); // 递归构造右子树
return root; // 返回当前子树的根节点
} // 递归函数结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只创建一次。 空间复杂度：O(n)，哈希表和递归栈会占用额外空间。
面试记忆
IMPORTANT
前序负责告诉你：当前根是谁。 中序负责告诉你：左子树和右子树的范围在哪里。
验证二叉搜索树
验证二叉搜索树
二叉搜索树 BST 的规则不是“左孩子小于我，右孩子大于我”这么简单，而是：
左子树所有节点 < 当前节点 < 右子树所有节点所以验证 BST 时，最稳的写法是：递归时带上下界。
核心思路
比如这棵树：
10
/ \
5 15
/ \
6 20很多新手会误判成合法，因为：
c
5 < 10
15 > 10
6 < 15
20 > 15但它其实不是 BST，因为 6 在 10 的右子树里，必须大于 10，可是 6 < 10。
所以递归时要传范围：
根节点 10：范围是 (-∞, +∞)
左子树 5：范围是 (-∞, 10)
右子树 15：范围是 (10, +∞)
节点 6：范围是 (10, 15)，但 6 不在这个范围里C# 代码
c
public class TreeNode // 定义二叉树节点类
{ // 节点类开始
public int val; // 当前节点的值
public TreeNode left; // 当前节点的左子节点
public TreeNode right; // 当前节点的右子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) // 定义构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.left = left; // 初始化左子节点
this.right = right; // 初始化右子节点
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public bool IsValidBST(TreeNode root) // 定义验证二叉搜索树的方法
{ // 方法开始
return Check(root, long.MinValue, long.MaxValue); // 从根节点开始，用 long 的最小值和最大值作为初始范围
} // 方法结束
private bool Check(TreeNode node, long min, long max) // 定义递归检查函数，min 和 max 表示当前节点允许的取值范围
{ // 递归函数开始
if (node == null) // 如果当前节点为空
{ // 空节点判断开始
return true; // 空树天然是合法的二叉搜索树
} // 空节点判断结束
if (node.val <= min || node.val >= max) // 如果当前节点不在合法范围内
{ // 范围判断开始
return false; // 当前节点不合法，整棵树直接不合法
} // 范围判断结束
bool leftOk = Check(node.left, min, node.val); // 检查左子树，左子树的最大值必须小于当前节点
bool rightOk = Check(node.right, node.val, max); // 检查右子树，右子树的最小值必须大于当前节点
return leftOk && rightOk; // 左右子树都合法，当前子树才合法
} // 递归函数结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只检查一次。 空间复杂度：O(h)，h 是树的高度，主要来自递归栈。
面试记忆
IMPORTANT
验证 BST 不能只比较父子节点。 要么用 中序遍历严格递增，要么用 递归上下界。 面试里我更推荐说上下界法，因为它能直接解释“祖先约束”。
二叉搜索树第 K 小元素
二叉搜索树第 K 小元素
这题的核心是：BST 的中序遍历结果一定是升序序列。
BST 满足：
左子树 < 根 < 右子树中序遍历顺序是：
左 -> 根 -> 右所以对 BST 做中序遍历，访问到的节点顺序就是从小到大。 第 k 次访问到的节点，就是第 k 小元素。
例子
5
/ \
3 6
/ \
2 4
/
1中序遍历结果是：
c
[1, 2, 3, 4, 5, 6]如果 k = 3，答案就是 3。
C# 代码：迭代中序遍历
c
using System.Collections.Generic; // 引入 Stack 栈集合类型
public class TreeNode // 定义二叉树节点类
{ // 节点类开始
public int val; // 当前节点的值
public TreeNode left; // 当前节点的左子节点
public TreeNode right; // 当前节点的右子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) // 定义构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.left = left; // 初始化左子节点
this.right = right; // 初始化右子节点
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public int KthSmallest(TreeNode root, int k) // 定义寻找 BST 第 k 小元素的方法
{ // 方法开始
Stack<TreeNode> stack = new Stack<TreeNode>(); // 创建栈，用来模拟递归中序遍历
TreeNode current = root; // current 表示当前正在遍历的节点
while (current != null || stack.Count > 0) // 当前节点不为空或者栈不为空时继续遍历
{ // 外层循环开始
while (current != null) // 一直向左走，找到当前子树最小的节点
{ // 内层循环开始
stack.Push(current); // 把当前节点压入栈中，等左子树处理完再访问它
current = current.left; // 继续走向左子节点
} // 内层循环结束
current = stack.Pop(); // 弹出栈顶节点，这就是当前应该访问的节点
k--; // 每访问一个节点，说明找到了一个更小排名的元素
if (k == 0) // 如果已经访问到第 k 个节点
{ // 判断开始
return current.val; // 当前节点的值就是第 k 小元素
} // 判断结束
current = current.right; // 访问完当前节点后，转向它的右子树
} // 外层循环结束
return -1; // 正常题目保证 k 合法，这一行理论上不会执行
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(h + k)。 h 是树高，因为先走到最左边要压栈；之后访问到第 k 个节点就可以提前停止。
空间复杂度：O(h)。 栈里最多存一条从根到叶子的路径。
面试记忆
NOTE
这题不要把整棵树转成数组再取第 k 个。 更好的说法是：中序遍历 BST 是升序，访问一个节点就 k--，k 为 0 时返回。
路径总和
路径总和
这题通常指：判断二叉树里是否存在一条 从根节点到叶子节点 的路径，使路径上的节点值之和等于 targetSum。
注意两个条件：
1. 必须从 root 开始
2. 必须到叶子节点结束中间某一段凑够了不算。
核心思路
每往下走一个节点，就把目标值减掉当前节点值。
比如目标值是 22：
5 -> 4 -> 11 -> 2计算过程可以理解成：
c
22 - 5 = 17
17 - 4 = 13
13 - 11 = 2
最后走到叶子节点 2，刚好等于剩余值 2所以返回 true。
C# 代码
c
public class TreeNode // 定义二叉树节点类
{ // 节点类开始
public int val; // 当前节点的值
public TreeNode left; // 当前节点的左子节点
public TreeNode right; // 当前节点的右子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) // 定义构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.left = left; // 初始化左子节点
this.right = right; // 初始化右子节点
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public bool HasPathSum(TreeNode root, int targetSum) // 定义判断路径总和的方法
{ // 方法开始
if (root == null) // 如果当前节点为空
{ // 空节点判断开始
return false; // 空节点无法形成根到叶子的路径
} // 空节点判断结束
if (root.left == null && root.right == null) // 如果当前节点是叶子节点
{ // 叶子节点判断开始
return root.val == targetSum; // 判断叶子节点值是否刚好等于剩余目标值
} // 叶子节点判断结束
int remain = targetSum - root.val; // 用目标值减去当前节点值，得到子节点需要凑出的剩余值
bool leftHasPath = HasPathSum(root.left, remain); // 递归判断左子树是否存在合法路径
bool rightHasPath = HasPathSum(root.right, remain); // 递归判断右子树是否存在合法路径
return leftHasPath || rightHasPath; // 左子树或右子树任意一边存在合法路径即可
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，最坏情况下每个节点都要看一次。 空间复杂度：O(h)，h 是树的高度，主要来自递归调用栈。
面试记忆
NOTE
这题不是求任意路径和，而是 根到叶子路径和。 递归时记住一句话：当前节点吃掉一部分 target，剩下的交给左右子树。
二叉树直径
二叉树直径
二叉树直径指的是：二叉树中任意两个节点之间最长路径的长度。
注意：这条最长路径 不一定经过根节点。 所以我们不能只算根节点左边多深、右边多深，而是要让 每个节点都尝试成为最长路径的拐点。
核心思路
对每个节点来说：
经过当前节点的最长路径 = 左子树高度 + 右子树高度比如：
1
/ \
2 3
/ \
4 5最长路径可以是：
c
4 -> 2 -> 1 -> 3这条路径有 3 条边，所以直径是 3。
DFS 的时候做两件事：
1. 返回当前节点的高度
2. 用 leftHeight + rightHeight 更新最大直径C# 代码
c
public class TreeNode // 定义二叉树节点类
{ // 节点类开始
public int val; // 当前节点的值
public TreeNode left; // 当前节点的左子节点
public TreeNode right; // 当前节点的右子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) // 定义构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.left = left; // 初始化左子节点
this.right = right; // 初始化右子节点
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
private int maxDiameter; // 记录当前找到的最大直径
public int DiameterOfBinaryTree(TreeNode root) // 定义求二叉树直径的方法
{ // 方法开始
maxDiameter = 0; // 初始化最大直径为 0
GetHeight(root); // 通过 DFS 计算高度，同时更新最大直径
return maxDiameter; // 返回最终最大直径
} // 方法结束
private int GetHeight(TreeNode node) // 定义求当前节点高度的方法
{ // 方法开始
if (node == null) // 如果当前节点为空
{ // 空节点判断开始
return 0; // 空节点高度为 0
} // 空节点判断结束
int leftHeight = GetHeight(node.left); // 递归求左子树高度
int rightHeight = GetHeight(node.right); // 递归求右子树高度
int currentDiameter = leftHeight + rightHeight; // 经过当前节点的最长路径长度
maxDiameter = System.Math.Max(maxDiameter, currentDiameter); // 用当前路径长度更新最大直径
return System.Math.Max(leftHeight, rightHeight) + 1; // 返回当前节点的高度
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只访问一次。 空间复杂度：O(h)，h 是树的高度，主要来自递归调用栈。
面试记忆
WARNING
DFS 返回的是 高度。 全局答案更新的是 左高度 + 右高度。 因为这表示：从左子树最深处，经过当前节点，再到右子树最深处的路径长度。
拓扑排序
拓扑排序
拓扑排序用来解决 有依赖关系的排序问题。
比如：
A 必须在 B 前面
B 必须在 C 前面那合法顺序可以是：
c
A -> B -> C在图里，如果有一条边：
c
u -> v意思就是：u 必须排在 v 前面。
核心思路：入度 + 队列
入度就是：有多少条边指向当前节点。
入度为 0：没有前置依赖，可以先做
入度不为 0：还有前置任务没完成，暂时不能做流程：
1. 统计每个节点的入度
2. 把所有入度为 0 的节点放进队列
3. 每次弹出一个节点，加入结果
4. 删除它指向别人的边，也就是让后继节点入度减 1
5. 如果某个后继节点入度变成 0，就加入队列
6. 最后如果结果数量少于节点数量，说明有环C# 代码
c
using System.Collections.Generic; // 引入 List 和 Queue 等集合类型
public class Solution // 定义题解类
{ // 类开始
public List<int> TopologicalSort(int nodeCount, int[][] edges) // 定义拓扑排序方法，nodeCount 是节点数量，edges 是有向边
{ // 方法开始
List<int>[] graph = new List<int>[nodeCount]; // 创建邻接表，用来保存每个节点指向哪些节点
int[] indegree = new int[nodeCount]; // 创建入度数组，记录每个节点有多少前置依赖
for (int i = 0; i < nodeCount; i++) // 遍历所有节点
{ // 循环开始
graph[i] = new List<int>(); // 给每个节点初始化一个邻接列表
} // 循环结束
for (int i = 0; i < edges.Length; i++) // 遍历所有有向边
{ // 循环开始
int from = edges[i][0]; // 取出边的起点
int to = edges[i][1]; // 取出边的终点
graph[from].Add(to); // 在邻接表中记录 from 指向 to
indegree[to]++; // 因为有一条边指向 to，所以 to 的入度加一
} // 循环结束
Queue<int> queue = new Queue<int>(); // 创建队列，用来保存当前入度为 0 的节点
for (int i = 0; i < nodeCount; i++) // 遍历所有节点
{ // 循环开始
if (indegree[i] == 0) // 如果当前节点没有前置依赖
{ // 判断开始
queue.Enqueue(i); // 把当前节点加入队列
} // 判断结束
} // 循环结束
List<int> result = new List<int>(); // 创建结果列表，用来保存拓扑排序结果
while (queue.Count > 0) // 只要队列中还有可以处理的节点
{ // 循环开始
int current = queue.Dequeue(); // 弹出一个入度为 0 的节点
result.Add(current); // 把当前节点加入拓扑排序结果
for (int i = 0; i < graph[current].Count; i++) // 遍历当前节点指向的所有后继节点
{ // 循环开始
int next = graph[current][i]; // 取出一个后继节点
indegree[next]--; // 删除 current 指向 next 的边，所以 next 入度减一
if (indegree[next] == 0) // 如果 next 的所有前置依赖都已经处理完
{ // 判断开始
queue.Enqueue(next); // 把 next 加入队列等待处理
} // 判断结束
} // 循环结束
} // 循环结束
if (result.Count != nodeCount) // 如果没有处理完所有节点
{ // 判断开始
return new List<int>(); // 说明图中有环，无法完成拓扑排序，返回空列表
} // 判断结束
return result; // 返回拓扑排序结果
} // 方法结束
} // 类结束复杂度
时间复杂度：O(V + E)，V 是节点数，E 是边数。 空间复杂度：O(V + E)，主要是邻接表、入度数组和队列。
面试记忆
CAUTION
拓扑排序一句话：入度为 0 的先做，做完就删掉它的出边。 如果最后还有节点没处理完，说明它们互相依赖，图里有环。
课程表
课程表
这题是拓扑排序的经典应用：判断课程依赖图里有没有环。
如果有环，比如：
学 0 之前要先学 1
学 1 之前又要先学 0那就永远无法开始，说明不能完成所有课程。
核心思路
prerequisites[i] = [a, b] 的意思是：
想学 a，必须先学 b所以建边是：
c
b -> a然后用入度表：
入度 = 当前课程还有几门前置课没学流程：
1. 建图，统计每门课的入度
2. 把入度为 0 的课程放入队列
3. 每次从队列取一门课，表示学完它
4. 它指向的后续课程入度减 1
5. 如果某门课入度变成 0，就加入队列
6. 最后看学完的课程数量是否等于 numCoursesC# 代码
c
using System.Collections.Generic; // 引入 List 和 Queue 等集合类型
public class Solution // 定义题解类
{ // 类开始
public bool CanFinish(int numCourses, int[][] prerequisites) // 定义判断是否能完成所有课程的方法
{ // 方法开始
List<int>[] graph = new List<int>[numCourses]; // 创建邻接表，graph[i] 表示学完课程 i 后可以学哪些课程
int[] indegree = new int[numCourses]; // 创建入度数组，indegree[i] 表示课程 i 还有几门前置课程
for (int i = 0; i < numCourses; i++) // 遍历所有课程
{ // 循环开始
graph[i] = new List<int>(); // 初始化每门课程对应的后续课程列表
} // 循环结束
for (int i = 0; i < prerequisites.Length; i++) // 遍历所有先修关系
{ // 循环开始
int course = prerequisites[i][0]; // 取出要学习的课程
int preCourse = prerequisites[i][1]; // 取出它的先修课程
graph[preCourse].Add(course); // 建边 preCourse -> course，表示学完 preCourse 才能学 course
indegree[course]++; // course 多了一门前置课程，所以入度加一
} // 循环结束
Queue<int> queue = new Queue<int>(); // 创建队列，用来保存当前可以学习的课程
for (int i = 0; i < numCourses; i++) // 遍历所有课程
{ // 循环开始
if (indegree[i] == 0) // 如果当前课程没有任何前置课程
{ // 判断开始
queue.Enqueue(i); // 当前课程可以立即学习，加入队列
} // 判断结束
} // 循环结束
int learnedCount = 0; // 记录已经学完的课程数量
while (queue.Count > 0) // 只要还有可以学习的课程
{ // 循环开始
int current = queue.Dequeue(); // 取出一门当前可以学习的课程
learnedCount++; // 学完这门课，已学课程数量加一
for (int i = 0; i < graph[current].Count; i++) // 遍历学完 current 后可以解锁的课程
{ // 循环开始
int next = graph[current][i]; // 取出一门后续课程
indegree[next]--; // current 已经学完，所以 next 少了一门未完成的前置课程
if (indegree[next] == 0) // 如果 next 的所有前置课程都学完了
{ // 判断开始
queue.Enqueue(next); // next 现在可以学习，加入队列
} // 判断结束
} // 循环结束
} // 循环结束
return learnedCount == numCourses; // 如果学完数量等于课程总数，说明可以完成所有课程
} // 方法结束
} // 类结束复杂度
时间复杂度：O(V + E)，V 是课程数，E 是先修关系数。 空间复杂度：O(V + E)，主要是邻接表、入度数组和队列。
面试记忆
IMPORTANT
课程表就是：拓扑排序判断有向图是否有环。 [a, b] 一定要记住是：先学 b，再学 a，所以建边 b -> a。
最小生成树
最小生成树
最小生成树 MST 解决的是：用最小总代价，把所有点连起来，并且不能形成环。
它通常出现在：
修路最小成本
网络布线最小成本
连接所有城市的最小费用
核心思路：Kruskal
Kruskal 很适合面试手写：
1. 把所有边按权重从小到大排序
2. 从最小的边开始尝试选择
3. 如果这条边连接的是两个不同集合，就选它
4. 如果这条边会形成环，就跳过
5. 选够 n - 1 条边时结束判断是否成环，用 并查集 Union-Find。
C# 代码
c
using System; // 引入基础系统命名空间
using System.Collections.Generic; // 引入 List 集合类型
public class Edge // 定义边类
{ // 边类开始
public int From; // 边的起点
public int To; // 边的终点
public int Weight; // 边的权重
public Edge(int from, int to, int weight) // 定义边的构造函数
{ // 构造函数开始
From = from; // 初始化起点
To = to; // 初始化终点
Weight = weight; // 初始化权重
} // 构造函数结束
} // 边类结束
public class UnionFind // 定义并查集类
{ // 并查集类开始
private int[] parent; // parent[i] 表示 i 的父节点
private int[] rank; // rank[i] 表示集合树的大致高度
public UnionFind(int n) // 定义并查集构造函数
{ // 构造函数开始
parent = new int[n]; // 创建父节点数组
rank = new int[n]; // 创建秩数组
for (int i = 0; i < n; i++) // 初始化每个节点
{ // 循环开始
parent[i] = i; // 每个节点一开始的父节点都是自己
rank[i] = 0; // 每个集合一开始高度为 0
} // 循环结束
} // 构造函数结束
public int Find(int x) // 查找 x 所在集合的根节点
{ // 查找函数开始
if (parent[x] != x) // 如果 x 不是根节点
{ // 判断开始
parent[x] = Find(parent[x]); // 路径压缩，让 x 直接指向根节点
} // 判断结束
return parent[x]; // 返回 x 所在集合的根节点
} // 查找函数结束
public bool Union(int a, int b) // 合并 a 和 b 所在的两个集合
{ // 合并函数开始
int rootA = Find(a); // 找到 a 的根节点
int rootB = Find(b); // 找到 b 的根节点
if (rootA == rootB) // 如果两个点已经在同一个集合
{ // 判断开始
return false; // 再连接会形成环，所以合并失败
} // 判断结束
if (rank[rootA] < rank[rootB]) // 如果 A 集合高度更低
{ // 判断开始
parent[rootA] = rootB; // 把 A 集合挂到 B 集合下面
} // 判断结束
else if (rank[rootA] > rank[rootB]) // 如果 B 集合高度更低
{ // 判断开始
parent[rootB] = rootA; // 把 B 集合挂到 A 集合下面
} // 判断结束
else // 如果两个集合高度一样
{ // 分支开始
parent[rootB] = rootA; // 把 B 集合挂到 A 集合下面
rank[rootA]++; // A 集合高度加一
} // 分支结束
return true; // 合并成功，说明这条边可以选择
} // 合并函数结束
} // 并查集类结束
public class Solution // 定义题解类
{ // 题解类开始
public int MinimumSpanningTree(int n, int[][] edges) // 定义求最小生成树总权重的方法
{ // 方法开始
List<Edge> edgeList = new List<Edge>(); // 创建边列表
for (int i = 0; i < edges.Length; i++) // 遍历输入的所有边
{ // 循环开始
int from = edges[i][0]; // 取出边的起点
int to = edges[i][1]; // 取出边的终点
int weight = edges[i][2]; // 取出边的权重
edgeList.Add(new Edge(from, to, weight)); // 把边加入边列表
} // 循环结束
edgeList.Sort((a, b) => a.Weight.CompareTo(b.Weight)); // 按边权从小到大排序
UnionFind unionFind = new UnionFind(n); // 创建并查集
int totalWeight = 0; // 记录最小生成树的总权重
int selectedCount = 0; // 记录已经选中的边数量
for (int i = 0; i < edgeList.Count; i++) // 从小到大遍历所有边
{ // 循环开始
Edge edge = edgeList[i]; // 取出当前边
if (unionFind.Union(edge.From, edge.To)) // 如果当前边连接的是两个不同集合
{ // 判断开始
totalWeight += edge.Weight; // 把当前边权重加入答案
selectedCount++; // 选中的边数量加一
if (selectedCount == n - 1) // 如果已经选够 n - 1 条边
{ // 判断开始
break; // 最小生成树已经完成，退出循环
} // 判断结束
} // 判断结束
} // 循环结束
if (selectedCount != n - 1) // 如果最后没有选够 n - 1 条边
{ // 判断开始
return -1; // 说明图不连通，无法生成最小生成树
} // 判断结束
return totalWeight; // 返回最小生成树的总权重
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(E log E)，主要花在边排序上。 空间复杂度：O(V + E)，主要是边列表和并查集。
面试记忆
TIP
最小生成树有三个关键词：连通所有点、不能有环、总代价最小。 Kruskal 的口诀是：边从小到大选，能连不同集合就选，会成环就跳过。
单词接龙
单词接龙
这题本质是：在一个隐式图里做 BFS 最短路。
每个单词是一个节点。 如果两个单词只差一个字母，它们之间就有一条边。 因为每次转换的代价都是 1，所以用 BFS，第一次遇到 endWord 时就是最短路径。
例子
c
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]一条最短路径是：
c
hit -> hot -> dot -> dog -> cog返回 5，因为题目要的是 接龙序列里的单词数量，不是修改次数。
C# 代码
c
using System.Collections.Generic; // 引入 HashSet、Queue、IList 等集合类型
public class Solution // 定义题解类
{ // 类开始
public int LadderLength(string beginWord, string endWord, IList<string> wordList) // 定义求最短接龙长度的方法
{ // 方法开始
HashSet<string> wordSet = new HashSet<string>(wordList); // 把 wordList 放进哈希表，方便 O(1) 查询单词是否存在
if (!wordSet.Contains(endWord)) // 如果终点单词不在字典里
{ // 判断开始
return 0; // 无论怎么转换都到不了终点，直接返回 0
} // 判断结束
Queue<string> queue = new Queue<string>(); // 创建 BFS 队列
queue.Enqueue(beginWord); // 把起点单词加入队列
HashSet<string> visited = new HashSet<string>(); // 创建访问集合，避免重复搜索同一个单词
visited.Add(beginWord); // 标记起点单词已经访问过
int step = 1; // step 表示当前接龙长度，起点本身算 1 个单词
while (queue.Count > 0) // 只要队列不为空，就继续 BFS
{ // 外层循环开始
int count = queue.Count; // 固定当前层的单词数量
for (int i = 0; i < count; i++) // 遍历当前 BFS 层的所有单词
{ // for 循环开始
string current = queue.Dequeue(); // 取出当前单词
if (current == endWord) // 如果当前单词已经是终点单词
{ // 判断开始
return step; // 返回当前 BFS 层数，也就是最短接龙长度
} // 判断结束
char[] chars = current.ToCharArray(); // 把当前单词转成字符数组，方便修改某一位
for (int index = 0; index < chars.Length; index++) // 枚举要修改的字符位置
{ // 位置循环开始
char originalChar = chars[index]; // 保存当前位置原来的字符
for (char c = 'a'; c <= 'z'; c++) // 尝试把当前位置替换成 a 到 z
{ // 字符循环开始
if (c == originalChar) // 如果替换后的字符和原字符一样
{ // 判断开始
continue; // 没有产生新单词，直接跳过
} // 判断结束
chars[index] = c; // 修改当前位置字符
string next = new string(chars); // 生成新的候选单词
if (wordSet.Contains(next) && !visited.Contains(next)) // 如果候选单词在字典中，并且还没有访问过
{ // 判断开始
visited.Add(next); // 标记候选单词已经访问
queue.Enqueue(next); // 把候选单词加入队列，等待下一层 BFS
} // 判断结束
} // 字符循环结束
chars[index] = originalChar; // 恢复当前位置字符，避免影响下一轮修改
} // 位置循环结束
} // for 循环结束
step++; // 当前层处理完，进入下一层，接龙长度加一
} // 外层循环结束
return 0; // BFS 结束仍然没有找到终点，说明无法转换
} // 方法结束
} // 类结束复杂度
时间复杂度：常见面试口径是 O(N * L * 26)。 N 是单词数量，L 是单词长度。
空间复杂度：O(N)。 主要是 wordSet、visited 和 BFS 队列。
面试记忆
NOTE
单词接龙就是：隐式图 + BFS 最短路。 每次枚举一个单词的每一位，把它替换成 a-z，能在字典中找到的新单词就是邻居。