算法入门第六篇：树与二叉树：非线性结构之美

技术文档

引言：树形结构的意义

朋友，我们一路走来，从线性结构的数组、链表，到栈、队列和堆这些高效容器，再到哈希表和各类排序算法，我们处理的数据都是以某种线性或平面化的方式组织。然而，现实世界中的许多数据，天生就具有层级（Hierarchical）关系，它们无法简单地用线性结构来描述。这时，我们就需要引入非线性结构——树（Tree）。

树，顾名思义，就像自然界中的树一样，从一个根（Root）开始，枝繁叶茂，向下伸展出多个分支。在计算机科学中，树形结构完美地映射了这种层级关系：

文件系统：你的电脑硬盘上的文件夹和文件，就构成了一棵典型的树。根目录是树根，每个文件夹是一个节点，它可能包含子文件夹或文件（子节点）。
HTML/XML 文档对象模型（DOM 树）：网页的结构就是一棵 DOM 树，每个 HTML 元素都是树上的一个节点，父子关系清晰。
游戏场景中的物体层级（GameObject Hierarchy in Unity）：在 Unity 中，所有的 GameObject 都可以有父子关系。一个父级 GameObject 下挂载多个子级 GameObject，这正是典型的树形结构。例如，一个角色模型可能由骨骼、网格、武器等子对象构成，它们之间就是父子关系。
组织架构图、家谱、决策树等等，都是树形结构的现实映射。

理解树，特别是二叉树（Binary Tree），是掌握复杂数据组织和高效算法的关键。它将帮助我们处理那些具有层级关系的数据，并能衍生出很多高效的查找、插入和删除策略。

树的基础概念

在深入二叉树之前，我们先来明确一些树的基本术语：

根（Root）：树中最顶层的节点，没有父节点。一棵树只有一个根节点。
节点（Node）：树中的一个数据元素。
父节点（Parent Node）：拥有子节点的节点。
子节点（Child Node）：一个节点直接相连的下一个层级的节点。
兄弟节点（Sibling Node）：具有相同父节点的节点。
叶子节点（Leaf Node）：没有子节点的节点。
度（Degree）：一个节点拥有的子节点的数量。树的度是所有节点度中的最大值。
边（Edge）：连接两个节点的线。
路径（Path）：从一个节点到另一个节点所经过的节点序列。
深度（Depth）：从根节点到某个节点的边的数量。根节点的深度为 0。
高度（Height）：从某个节点到其最远叶子节点的最长路径上的边数。叶子节点的高度为 0。树的高度是根节点的高度。
层（Level）：节点的深度加 1。根节点在第 1 层。

二叉树（Binary Tree）

定义：

二叉树是一种特殊的树，它的每个节点最多只有两个子节点，通常区分为左子节点（Left Child）和右子节点（Right Child）。二叉树在实际应用中非常广泛，是树形结构中最基础也是最重要的类型。

特殊类型

满二叉树（Full Binary Tree）：除了叶子节点外，所有节点都有两个子节点，并且所有叶子节点都在同一层。一个完美对称的三角形。
完全二叉树（Complete Binary Tree）：除了最后一层外，其他层的节点都是满的，并且最后一层的节点从左向右依次排列，不允许中间有空缺。
- 特点：可以使用数组来存储，无需指针，节省空间且访问高效。堆（Heap）就是一种完全二叉树。
平衡二叉树（Balanced Binary Tree）：左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是平衡二叉树。平衡二叉树能有效避免树退化成链表，从而保证查找、插入、删除等操作的对数时间复杂度。常见的有 AVL 树和红黑树。

二叉树遍历

遍历二叉树是指按照一定的顺序访问树中的每个节点。二叉树的遍历方法主要分为两大类：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是沿着树的深度方向进行遍历，直到不能再深入为止，然后回溯到上一个节点，再探索其他分支。二叉树的 DFS 通常有三种方式：前序遍历、中序遍历和后序遍历。

所有三种遍历方式都可以通过**递归（Recursion）和迭代（Iteration）两种方式实现。递归实现简洁，但可能会有栈溢出风险；迭代实现需要手动使用栈（Stack）**来模拟递归栈。

1. 前序遍历（Preorder Traversal）：根-左-右

访问顺序：先访问根节点，然后递归地访问左子树，最后递归地访问右子树。
用途：常用于复制一棵树、创建表达式树。

递归实现：

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 static IList PreorderTraversal(TreeNode root) { IList result = new List(); PreorderHelper(root, result); return result;}private static void PreorderHelper(TreeNode node, IList result) { if (node == null) { return; } result.Add(node.val); // 访问根节点 PreorderHelper(node.left, result); // 递归遍历左子树 PreorderHelper(node.right, result); // 递归遍历右子树}

迭代实现（利用栈）：

创建一个栈，将根节点压入栈。
循环直到栈为空：

a. 弹出栈顶节点，访问它，并将其值加入结果列表。

b. 如果该节点的右子节点不为空，将其压入栈（先右后左，因为栈是LIFO，要先处理左子树）。

c. 如果该节点的左子节点不为空，将其压入栈。

public static IList PreorderTraversalIterative(TreeNode root) { IList result = new List(); if (root == null) { return result; } Stack stack = new Stack(); stack.Push(root); // 将根节点压入栈 while (stack.Count > 0) { TreeNode node = stack.Pop(); // 弹出栈顶节点（当前节点） result.Add(node.val); // 访问当前节点 // 先压右子节点，再压左子节点，这样左子节点会先被弹出处理 if (node.right != null) { stack.Push(node.right); } if (node.left != null) { stack.Push(node.left); } } return result;}

2. 中序遍历（Inorder Traversal）：左-根-右

访问顺序：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。
用途：**二叉搜索树（BST）的中序遍历结果是升序排列的。**这是其最重要的特性。

递归实现：

public static IList InorderTraversal(TreeNode root) { IList result = new List(); InorderHelper(root, result); return result;}private static void InorderHelper(TreeNode node, IList result) { if (node == null) { return; } InorderHelper(node.left, result); // 递归遍历左子树 result.Add(node.val); // 访问根节点 InorderHelper(node.right, result); // 递归遍历右子树}

迭代实现（利用栈）：

初始化 current = root，创建一个栈。
循环直到 current 不为空或者栈不为空：

a. 将 current 及其所有左子节点压入栈，直到 current 为空。

b. 弹出栈顶节点，访问它，并将其值加入结果列表。

c. 将 current 更新为弹出节点的右子节点，以便处理右子树。

public static IList InorderTraversalIterative(TreeNode root) { IList result = new List(); Stack stack = new Stack(); TreeNode current = root; while (current != null || stack.Count > 0) { // 将所有左子节点入栈 while (current != null) { stack.Push(current); current = current.left; } // 弹出栈顶（当前子树最左边的节点） current = stack.Pop(); result.Add(current.val); // 访问当前节点 // 转向处理右子树 current = current.right; } return result;}

3. 后序遍历（Postorder Traversal）：左-右-根

访问顺序：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。
用途：常用于删除树中的节点（先删除子节点，再删除父节点）。

递归实现：

public static IList PostorderTraversal(TreeNode root) { IList result = new List(); PostorderHelper(root, result); return result;}private static void PostorderHelper(TreeNode node, IList result) { if (node == null) { return; } PostorderHelper(node.left, result); // 递归遍历左子树 PostorderHelper(node.right, result); // 递归遍历右子树 result.Add(node.val); // 访问根节点}

迭代实现（利用栈，略复杂）：

后序遍历的迭代实现通常有两种方法，一种是使用两个栈，另一种是使用一个栈但需要额外记录上一个访问的节点。这里介绍使用两个栈的方法，它相对直观：
1. 创建两个栈 s1 和 s2。将根节点压入 s1。
2. 循环直到 s1 为空：
  
  a. 从 s1 弹出节点 node。
  
  b. 将 node 压入 s2。
  
  c. 如果 node 的左子节点不为空，将其压入 s1。
  
  d. 如果 node 的右子节点不为空，将其压入 s1。
3. 最后，将 s2 中的所有元素弹出并加入结果列表（此时 s2 中的顺序就是后序遍历的逆序，所以需要弹出加入）。
C#
```
public static IList PostorderTraversalIterative(TreeNode root) { IList result = new List(); if (root == null) { return result; } Stack s1 = new Stack(); Stack s2 = new Stack(); s1.Push(root); while (s1.Count > 0) { TreeNode node = s1.Pop(); s2.Push(node); // 将当前节点压入第二个栈 // 先压左子节点再压右子节点，以便 s1 弹出时先处理右子树 if (node.left != null) { s1.Push(node.left); } if (node.right != null) { s1.Push(node.right); } } // 将 s2 中的元素弹出，顺序就是后序遍历结果 while (s2.Count > 0) { result.Add(s2.Pop().val); } return result;}
```

广度优先搜索（BFS）：层序遍历（Level Order Traversal）

广度优先搜索是沿着树的宽度方向进行遍历，即先访问所有位于同一层的节点，然后再访问下一层的节点。

访问顺序：逐层访问，从上到下，从左到右。
实现：利用**队列（Queue）**实现。
1. 创建一个队列，将根节点加入队列。
2. 循环直到队列为空：
  
  a. 弹出队列头部节点，访问它，并将其值加入结果列表。
  
  b. 如果该节点的左子节点不为空，将其加入队列。
  
  c. 如果该节点的右子节点不为空，将其加入队列。

代码实现：

using System.Collections.Generic; // 引入 Queuepublic static IList<IList> LevelOrderTraversal(TreeNode root) { IList<IList> result = new List<IList>(); if (root == null) { return result; } Queue queue = new Queue(); queue.Enqueue(root); // 将根节点入队 while (queue.Count > 0) { int levelSize = queue.Count; // 当前层的节点数量 List currentLevelNodes = new List(); // 存储当前层的节点值 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.Dequeue(); // 弹出当前层的一个节点 currentLevelNodes.Add(node.val); // 访问并加入当前层列表 // 将其左右子节点（下一层的节点）入队 if (node.left != null) { queue.Enqueue(node.left); } if (node.right != null) { queue.Enqueue(node.right); } } result.Add(currentLevelNodes); // 将当前层的所有节点加入总结果 } return result;}

二叉搜索树（Binary Search Tree, BST）

定义：

**二叉搜索树（BST）**是一种特殊的二叉树，它满足以下特性：

左子树特性：若一个节点拥有左子节点，则其左子树中所有节点的值都小于该节点的值。
右子树特性：若一个节点拥有右子节点，则其右子树中所有节点的值都大于该节点的值。
无重复值：通常情况下，BST 不允许有重复值（或者约定重复值放在左子树或右子树）。

基本操作：

BST 的特性使得它非常适合进行高效的查找、插入和删除操作。在理想（平衡）情况下，这些操作的时间复杂度都为 O(logN)。

查找（Search）：
- 从根节点开始。
- 如果要查找的值小于当前节点的值，则在左子树中继续查找。
- 如果要查找的值大于当前节点的值，则在右子树中继续查找。
- 如果相等，则找到。如果到达空节点仍未找到，则不存在。
插入（Insertion）：
- 查找插入位置：从根节点开始，遵循查找路径，直到找到一个空位置（即查找失败）。
- 在该空位置创建新节点并插入。
删除（Deletion）：

删除操作相对复杂，需要考虑三种情况：
1. 删除叶子节点：直接删除。
2. 删除只有一个子节点的节点：用其子节点替换该节点。
3. 删除有两个子节点的节点：
  - 找到其右子树中的最小节点（或左子树中的最大节点），将其值复制到要删除的节点上。
  - 然后删除那个被复制的节点（此时它变成了情况 1 或 2）。

特性：中序遍历结果有序

这是 BST 最重要的特性之一。对任何 BST 进行中序遍历，得到的结果序列是升序排列的。这个特性在面试中经常用来验证一个二叉树是否是 BST，或用于排序。

经典面试题与解法

1. 反转二叉树（Invert Binary Tree）

题目描述：

翻转一棵二叉树。

示例：

输入:

4

/

2 7

/ \\ /

1 3 6 9

输出:

4

/

7 2

/ \\ /

9 6 3 1
解题思路：递归的优雅应用

反转二叉树意味着将每个节点的左右子节点进行交换。这是一个典型的递归问题。

步骤：
1. 基准情况：如果当前节点为空，直接返回 null。
2. 递归逻辑：
  
  a. 递归地反转当前节点的左子树。
  
  b. 递归地反转当前节点的右子树。
  
  c. 交换当前节点的左右子节点。
3. 返回当前节点。

代码实现：

public class Solution { public TreeNode InvertTree(TreeNode root) { if (root == null) { return null; } // 递归反转左右子树 TreeNode left = InvertTree(root.left); TreeNode right = InvertTree(root.right); // 交换当前节点的左右子节点 root.left = right; root.right = left; return root; }}

复杂度分析：
- 时间复杂度：O(N)，其中 N 是树中节点的数量。每个节点只被访问一次。
- 空间复杂度：O(H)，其中 H 是树的高度。这是递归栈所需的空间，在最坏情况下（退化为链表）是 O(N)，在最好情况下（平衡二叉树）是 O(logN)。

2. 二叉树的最大/最小深度（Maximum/Minimum Depth of Binary Tree）

题目描述：
- 最大深度：给定一个二叉树，找出其最大深度。最大深度是从根节点到最远叶子节点的最长路径上的节点数量。
- 最小深度：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
- 注意：叶子节点是指没有子节点的节点。

解题思路：BFS/DFS 解决

最大深度 (Maximum Depth)：DFS 递归

最大深度很容易用递归实现。一个节点的最大深度等于其左右子树的最大深度中的较大值，再加 1（加上自身）。

public class Solution { public int MaxDepth(TreeNode root) { if (root == null) { return 0; // 空树深度为 0 } int leftDepth = MaxDepth(root.left); // 左子树最大深度 int rightDepth = MaxDepth(root.right); // 右子树最大深度 return Math.Max(leftDepth, rightDepth) + 1; // 当前节点的最大深度 }}

复杂度： 时间 O(N)，空间 O(H)。

最小深度 (Minimum Depth)：BFS (层序遍历) 是最优解

最小深度是到最近叶子节点的路径。使用 BFS（层序遍历）是解决最小深度问题的最直观和高效的方法，因为 BFS 是逐层遍历的，第一个遇到的叶子节点所在的层数就是最小深度。

using System.Collections.Generic;using System;public class Solution { public int MinDepth(TreeNode root) { if (root == null) { return 0; } Queue queue = new Queue(); queue.Enqueue(root); int depth = 1; // 根节点是第一层 while (queue.Count > 0) { int levelSize = queue.Count; for (int i = 0; i < levelSize; i++) { TreeNode node = queue.Dequeue(); // 如果当前节点是叶子节点，则找到了最短路径 if (node.left == null && node.right == null) {  return depth; } if (node.left != null) {  queue.Enqueue(node.left); } if (node.right != null) {  queue.Enqueue(node.right); } } depth++; // 进入下一层 } return depth; // 理论上不会执行到这里，因为 root 不为 null }}

复杂度： 时间 O(N)（最坏情况下访问所有节点），空间 O(W)（W 是树的最大宽度，最坏 O(N)）。

最小深度 (Minimum Depth)：DFS 递归 (需要注意边界)

DFS 也能解决最小深度，但需要注意当某个子树为空时，不能直接取 Math.Min，因为空子树的深度是 0，会错误地认为是最小深度。

using System;public class Solution { public int MinDepthDFS(TreeNode root) { if (root == null) { return 0; } // 如果左子树为空，只看右子树的最小深度 if (root.left == null) { return MinDepthDFS(root.right) + 1; } // 如果右子树为空，只看左子树的最小深度 if (root.right == null) { return MinDepthDFS(root.left) + 1; } // 左右子树都不为空，取两者最小深度 return Math.Min(MinDepthDFS(root.left), MinDepthDFS(root.right)) + 1; }}

复杂度： 时间 O(N)，空间 O(H)。

思考： 对深度和广度遍历的理解，决定了你在解决这类问题时的选择。最大深度通常用 DFS 更简洁，最小深度用 BFS 更直观和有时更优。

3. 判断平衡二叉树（Balanced Binary Tree）

题目描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。

一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
解题思路：递归判断左右子树高度差

这道题需要我们同时计算子树高度并判断平衡性。如果分开计算高度再判断，会有很多重复计算。

一个更高效的方法是自底向上的递归：在计算子树高度的同时，判断其是否平衡。如果子树不平衡，则直接返回一个特殊值（例如 -1）表示不平衡，并逐层向上返回，避免不必要的计算。

步骤：
1. 定义一个辅助函数 GetDepth(TreeNode node)，它返回以 node 为根的子树的高度。
2. GetDepth 函数的逻辑：
  
  a. 基准情况：如果 node 为 null，返回 0。
  
  b. 递归：
  
  i. 递归调用 GetDepth(node.left) 获取左子树的高度 leftDepth。如果 leftDepth 为 -1（表示左子树不平衡），则当前树也不平衡，返回 -1。
  
  ii. 递归调用 GetDepth(node.right) 获取右子树的高度 rightDepth。如果 rightDepth 为 -1（表示右子树不平衡），则当前树也不平衡，返回 -1。
  
  iii. 判断当前节点是否平衡：如果 Math.Abs(leftDepth - rightDepth) > 1，则当前树不平衡，返回 -1。
  
  iv. 如果平衡，则返回当前节点的高度：Math.Max(leftDepth, rightDepth) + 1。
3. 主函数调用 GetDepth(root)。如果返回值为 -1，则不平衡；否则平衡。

代码实现：

using System;public class Solution { public bool IsBalanced(TreeNode root) { return GetDepth(root) != -1; } // 返回以 node 为根的子树高度，如果子树不平衡则返回 -1 private int GetDepth(TreeNode node) { if (node == null) { return 0; // 空节点高度为 0 } int leftDepth = GetDepth(node.left); if (leftDepth == -1) { // 左子树不平衡，直接返回 -1 return -1; } int rightDepth = GetDepth(node.right); if (rightDepth == -1) { // 右子树不平衡，直接返回 -1 return -1; } // 如果左右子树的高度差大于 1，则不平衡 if (Math.Abs(leftDepth - rightDepth) > 1) { return -1; } // 如果平衡，返回当前节点的高度 return Math.Max(leftDepth, rightDepth) + 1; }}

复杂度分析：
- 时间复杂度：O(N)。每个节点只被访问一次（在 GetDepth 函数中计算高度并判断平衡性）。
- 空间复杂度：O(H)。递归栈的深度，最坏情况下 O(N)，最好情况下 O(logN)。

4. 对称二叉树（Symmetric Tree）

题目描述：

给定一个二叉树，检查它是否是自身的镜像（即对称）。

示例：

输入:

1

/

2 2

/ \\ /

3 4 4 3

输出: true
解题思路：递归判断镜像对称

判断一个二叉树是否对称，实际上是判断它的左右子树是否互为镜像。这同样是一个递归问题。

步骤：
1. 定义一个辅助函数 IsMirror(TreeNode t1, TreeNode t2)，用于判断两棵树 t1 和 t2 是否互为镜像。
2. IsMirror 函数的逻辑：
  
  a. 基准情况：
  
  i. 如果 t1 和 t2 都为 null，则它们是对称的，返回 true。
  
  ii. 如果 t1 或 t2 中只有一个为 null，则不对称，返回 false。
  
  b. 递归逻辑：
  
  i. 判断 t1.val 是否等于 t2.val。
  
  ii. 递归判断 t1.left 是否与 t2.right 互为镜像。
  
  iii. 递归判断 t1.right 是否与 t2.left 互为镜像。
  
  iv. 三个条件都满足才返回 true。
3. 主函数调用 IsMirror(root.left, root.right)。

代码实现：

public class Solution { public bool IsSymmetric(TreeNode root) { if (root == null) { return true; // 空树是对称的 } return IsMirror(root.left, root.right); } // 辅助函数：判断两棵树是否互为镜像 private bool IsMirror(TreeNode t1, TreeNode t2) { // 两棵树都为空，对称 if (t1 == null && t2 == null) { return true; } // 只有一棵树为空，不对称 if (t1 == null || t2 == null) { return false; } // 根节点值不相等，不对称 if (t1.val != t2.val) { return false; } // 递归判断：t1 的左子树与 t2 的右子树镜像对称 // 并且 t1 的右子树与 t2 的左子树镜像对称 return IsMirror(t1.left, t2.right) && IsMirror(t1.right, t2.left); }}

复杂度分析：
- 时间复杂度：O(N)。每个节点最多被访问一次。
- 空间复杂度：O(H)。递归栈的深度。

5. 二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

对于有根树 T 的两个节点 p、q，最近公共祖先（LCA）是最小的节点 A，使得 A 既是 p 的祖先，也是 q 的祖先（这里我们允许一个节点是它自己的祖先）。
解题思路：递归法

这是二叉树问题中一个非常经典且重要的考题。LCA 的递归解法非常优雅。

核心思想：

对于一个节点 root 和两个目标节点 p, q：
1. 如果 root 为 null，或者 root 就是 p 或 q，那么 root 就是当前的 L CA（因为 LCA 可以是自身）。
2. 递归地在 root.left 查找 p 和 q 的 LCA，记为 leftLCA。
3. 递归地在 root.right 查找 p 和 q 的 LCA，记为 rightLCA。
4. 根据 leftLCA 和 rightLCA 的情况判断当前 root 是否是 LCA：
  
  a. 如果 leftLCA 和 rightLCA 都存在（都不为 null），说明 p 和 q 分别在 root 的左右子树中，那么 root 就是它们的 LCA。
  
  b. 如果 leftLCA 存在而 rightLCA 为 null，说明 p 和 q 都在 root 的左子树中，那么 leftLCA 就是它们的 LCA。
  
  c. 如果 rightLCA 存在而 leftLCA 为 null，说明 p 和 q 都在 root 的右子树中，那么 rightLCA 就是它们的 LCA。

代码实现：

public class Solution { public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 1. 基准情况：如果 root 为 null，或者 root 就是 p 或 q，直接返回 root if (root == null || root == p || root == q) { return root; } // 2. 递归查找左右子树的 LCA TreeNode leftLCA = LowestCommonAncestor(root.left, p, q); TreeNode rightLCA = LowestCommonAncestor(root.right, p, q); // 3. 根据左右子树的查找结果判断当前 root 是否是 LCA if (leftLCA != null && rightLCA != null) { // p 和 q 分别在 root 的左右子树中，所以 root 是 LCA return root; } else if (leftLCA != null) { // p 和 q 都在 root 的左子树中（或者 leftLCA 就是 p 或 q，另一个也在左子树） return leftLCA; } else { // rightLCA != null // p 和 q 都在 root 的右子树中 return rightLCA; } }}

复杂度分析：
- 时间复杂度：O(N)。在最坏情况下，我们可能需要访问树中的所有节点。
- 空间复杂度：O(H)。递归栈的深度。

6. 验证二叉搜索树（Validate Binary Search Tree）

题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

一个有效的二叉搜索树定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。

解题思路 1：中序遍历

利用 BST 的核心特性：中序遍历结果是升序的。

对二叉树进行中序遍历，将遍历结果存储到一个列表中。
检查列表中的元素是否严格升序。

代码实现 (中序遍历到列表再检查)：

using System.Collections.Generic;public class Solution { public bool IsValidBST(TreeNode root) { IList inorderList = new List(); InorderCollect(root, inorderList); // 执行中序遍历 // 检查中序遍历结果是否严格升序 for (int i = 1; i < inorderList.Count; i++) { if (inorderList[i] <= inorderList[i - 1]) { return false; } } return true; } private void InorderCollect(TreeNode node, IList list) { if (node == null) return; InorderCollect(node.left, list); list.Add(node.val); InorderCollect(node.right, list); }}

复杂度： 时间 O(N)，空间 O(N)（存储列表）。

优化：中序遍历 (不存储列表，只用一个变量记录前一个节点)

更优的实现方式是不创建额外的列表，而是在中序遍历过程中实时比较当前节点与前一个节点的值。

public class Solution { private long prev = long.MinValue; // 使用 long 来处理 int 的最小值，以防节点值为 int.MinValue public bool IsValidBST(TreeNode root) { return IsValidBSTInorder(root); } private bool IsValidBSTInorder(TreeNode node) { if (node == null) { return true; } // 递归左子树 if (!IsValidBSTInorder(node.left)) { return false; } // 访问根节点：检查当前节点值是否大于前一个节点值 if (node.val <= prev) { return false; } prev = node.val; // 更新 prev 为当前节点值 // 递归右子树 return IsValidBSTInorder(node.right); }}

复杂度： 时间 O(N)，空间 O(H) (递归栈)。

解题思路 2：递归上下界判断

这是最常见且高效的解法。在递归遍历过程中，为每个节点设置一个合法的值范围（min 和 max）。

步骤：
1. 定义一个辅助函数 IsValidBST(TreeNode node, long min, long max)。
2. IsValidBST 函数的逻辑：
  
  a. 基准情况：如果 node 为 null，返回 true。
  
  b. 判断当前节点值是否在合法范围内：
  
  如果 node.val = max，则不是有效的 BST，返回 false。
  
  c. 递归判断左右子树：
  
  i. 递归调用 IsValidBST(node.left, min, node.val)：左子树的上限是当前节点的值。
  
  ii. 递归调用 IsValidBST(node.right, node.val, max)：右子树的下限是当前节点的值。
  
  iii. 两个递归都返回 true 才返回 true。
3. 主函数调用 IsValidBST(root, long.MinValue, long.MaxValue)。

代码实现：

using System; // For long.MinValue, long.MaxValuepublic class Solution { public bool IsValidBST(TreeNode root) { // 初始调用时，根节点的范围是整个整数范围 return IsValidBSTRecursive(root, long.MinValue, long.MaxValue); } // 辅助函数：判断节点 node 是否在 (min, max) 范围内，并递归检查子树 private bool IsValidBSTRecursive(TreeNode node, long min, long max) { // 基准情况：空节点是有效的 BST if (node == null) { return true; } // 检查当前节点的值是否在合法范围内 if (node.val = max) { return false; } // 递归检查左子树：左子树的所有节点必须小于当前节点值 // 所以左子树的上限更新为当前节点值 bool isLeftValid = IsValidBSTRecursive(node.left, min, node.val); if (!isLeftValid) { return false; } // 递归检查右子树：右子树的所有节点必须大于当前节点值 // 所以右子树的下限更新为当前节点值 bool isRightValid = IsValidBSTRecursive(node.right, node.val, max); return isRightValid; }}

复杂度分析：
- 时间复杂度：O(N)。每个节点只被访问一次。
- 空间复杂度：O(H)。递归栈的深度。
思考： 验证 BST 的两种方法各有优劣。中序遍历法直观地利用了 BST 的核心性质，但额外空间消耗可能较大。递归上下界法通过参数传递范围，避免了额外空间，且效率更高。在面试中，通常会期望你能够实现递归上下界的方法。

总结与练习

本篇我们深入学习了树这一重要的非线性数据结构，并重点剖析了其最常见的形式——二叉树。我们掌握了树的基本概念，并详细了解了二叉树的各种遍历方式（前序、中序、后序的递归与迭代实现，以及层序遍历）。

我们还重点探讨了二叉搜索树（BST），理解了其核心特性（左小右大，中序遍历有序）以及查找、插入、删除等基本操作的原理。通过几个经典面试题的解析，我们进一步巩固了对二叉树性质和操作的理解。

本篇核心知识点回顾：

树的基础概念：根、节点、叶子、深度、高度等。
二叉树定义及特殊类型：满二叉树、完全二叉树、平衡二叉树。
二叉树遍历：
- DFS (深度优先搜索)：前序（根左右）、中序（左根右）、后序（左右根）的递归与迭代实现。理解栈在迭代中的作用。
- BFS (广度优先搜索)：层序遍历，利用队列实现。
二叉搜索树 (BST)：定义、查找/插入/删除操作，中序遍历有序的核心特性。
经典二叉树问题：反转二叉树、最大/最小深度、平衡二叉树、对称二叉树、最近公共祖先、验证二叉搜索树。

课后练习（推荐力扣 LeetCode 题目）：

二叉树的前/中/后序遍历：LeetCode 144 (前序)，LeetCode 94 (中序)，LeetCode 145 (后序)。务必练习递归和迭代两种实现。
二叉树的层序遍历：LeetCode 102。
反转二叉树 (Invert Binary Tree)：LeetCode 226。
二叉树的最大深度 (Maximum Depth of Binary Tree)：LeetCode 104。
二叉树的最小深度 (Minimum Depth of Binary Tree)：LeetCode 111。
平衡二叉树 (Balanced Binary Tree)：LeetCode 110。
对称二叉树 (Symmetric Tree)：LeetCode 101。
二叉搜索树的最近公共祖先 (Lowest Common Ancestor of a Binary Search Tree)：LeetCode 235（比普通二叉树更简单，因为 BST 特性）。
二叉树的最近公共祖先 (Lowest Common Ancestor of a Binary Tree)：LeetCode 236。
验证二叉搜索树 (Validate Binary Search Tree)：LeetCode 98。

树和二叉树是构建更复杂数据结构（如图、Trie 树等）的基础，也是很多高级算法（如图算法、动态规划）的前提。掌握好它们，你将能应对更多挑战。

算法入门第六篇：树与二叉树：非线性结构之美

引言：树形结构的意义

树的基础概念

二叉树（Binary Tree）

特殊类型

二叉树遍历

深度优先搜索（DFS）

1. 前序遍历（Preorder Traversal）：根-左-右

2. 中序遍历（Inorder Traversal）：左-根-右

3. 后序遍历（Postorder Traversal）：左-右-根

广度优先搜索（BFS）：层序遍历（Level Order Traversal）

二叉搜索树（Binary Search Tree, BST）

经典面试题与解法

1. 反转二叉树（Invert Binary Tree）

2. 二叉树的最大/最小深度（Maximum/Minimum Depth of Binary Tree）

3. 判断平衡二叉树（Balanced Binary Tree）

4. 对称二叉树（Symmetric Tree）

5. 二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）

6. 验证二叉搜索树（Validate Binary Search Tree）

总结与练习

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签

算法入门第六篇：树与二叉树：非线性结构之美

引言：树形结构的意义

树的基础概念

二叉树（Binary Tree）

特殊类型

二叉树遍历

深度优先搜索（DFS）

1. 前序遍历（Preorder Traversal）：根-左-右

2. 中序遍历（Inorder Traversal）：左-根-右

3. 后序遍历（Postorder Traversal）：左-右-根

广度优先搜索（BFS）：层序遍历（Level Order Traversal）

二叉搜索树（Binary Search Tree, BST）

经典面试题与解法

1. 反转二叉树（Invert Binary Tree）

2. 二叉树的最大/最小深度（Maximum/Minimum Depth of Binary Tree）

3. 判断平衡二叉树（Balanced Binary Tree）

4. 对称二叉树（Symmetric Tree）

5. 二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）

6. 验证二叉搜索树（Validate Binary Search Tree）

总结与练习

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签