算法编程题：树与二叉搜索树（8 题）
053 一次调用返回二叉树的前序、中序和后序遍历。
难度： 基础
方法签名： TreeNode? root
输入约束： 树结构无环
示例： 根 1，右子 2，2 的左子 3 → 前序[1,2,3]、中序[1,3,2]、后序[3,2,1]
目标复杂度： 时间 O(n)，额外空间 O(h) 不计结果
查看参考答案
解题思路： 一次 DFS 在访问节点、左子树后和右子树后分别记录值。
不变量： 递归返回时当前子树的三种遍历结果都已完整追加。
public static class AlgCode053Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static int[][] Solve(TreeNode? root)
{
var preorder = new List<int>();
var inorder = new List<int>();
var postorder = new List<int>();
Visit(root, preorder, inorder, postorder);
return [preorder.ToArray(), inorder.ToArray(), postorder.ToArray()];
}
private static void Visit(
TreeNode? node,
List<int> preorder,
List<int> inorder,
List<int> postorder)
{
if (node is null) return;
preorder.Add(node.Value);
Visit(node.Left, preorder, inorder, postorder);
inorder.Add(node.Value);
Visit(node.Right, preorder, inorder, postorder);
postorder.Add(node.Value);
}
}复杂度： 时间 O(n)，递归栈 O(h)，结果空间 O(n)。
边界用例： 空树；单节点；退化链形树。
面试追问：
- 如何用显式栈实现迭代中序遍历？
054 计算二叉树按节点数定义的最大深度。
难度： 基础
方法签名： TreeNode? root
输入约束： 空树深度为 0
示例： [3,9,20,null,null,15,7] → 3
目标复杂度： 时间 O(n)，额外空间 O(h)
查看参考答案
解题思路： 空节点返回零，非空节点返回左右最大深度加一。
不变量： 递归返回值等于当前子树从根到最深叶子的节点数。
public static class AlgCode054Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static int Solve(TreeNode? root)
{
if (root is null) return 0;
return 1 + Math.Max(Solve(root.Left), Solve(root.Right));
}
}复杂度： 时间 O(n)，递归栈 O(h)。
边界用例： 空树；单节点；退化链形树可能导致深递归。
面试追问：
- 如何用 BFS 迭代计算深度并避免递归栈？
055 按层返回二叉树每一层的节点值。
难度： 进阶
方法签名： TreeNode? root
输入约束： 树结构无环
示例： [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]
目标复杂度： 时间 O(n)，额外空间 O(w)
查看参考答案
解题思路： 队列按层出队，处理每层前记录当前队列长度。
不变量： 每轮开始时队列前 levelSize 个节点恰好属于当前层。
public static class AlgCode055Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static int[][] Solve(TreeNode? root)
{
if (root is null) return [];
var result = new List<int[]>();
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
int count = queue.Count;
var level = new int[count];
for (int index = 0; index < count; index++)
{
TreeNode node = queue.Dequeue();
level[index] = node.Value;
if (node.Left is not null) queue.Enqueue(node.Left);
if (node.Right is not null) queue.Enqueue(node.Right);
}
result.Add(level);
}
return result.ToArray();
}
}复杂度： 时间 O(n)，队列峰值空间 O(w)，结果空间 O(n)。
边界用例： 空树；单节点；极宽层。
面试追问：
- 如何改为锯齿形层序遍历？
056 验证一棵树是否为严格二叉搜索树。
难度： 进阶
方法签名： TreeNode? root
输入约束： 严格 BST 不允许重复值
示例： [5,1,4,null,null,3,6] → false
目标复杂度： 时间 O(n)，额外空间 O(h)
查看参考答案
解题思路： 递归传递当前节点允许的 long 下界和上界。
不变量： 进入节点时，祖先约束已经合并为当前有效开区间。
public static class AlgCode056Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static bool Solve(TreeNode? root)
=> Validate(root, long.MinValue, long.MaxValue);
private static bool Validate(TreeNode? node, long lower, long upper)
{
if (node is null) return true;
if (node.Value <= lower || node.Value >= upper) return false;
return Validate(node.Left, lower, node.Value) &&
Validate(node.Right, node.Value, upper);
}
}复杂度： 时间 O(n)，递归栈 O(h)。
边界用例： 空树；int 边界；跨层违规；重复值。
面试追问：
- 如果允许重复值统一放在右子树，边界条件如何修改？
057 原地翻转二叉树的左右子树。
难度： 进阶
方法签名： TreeNode? root
输入约束： 树结构无环，允许修改节点
示例： [4,2,7,1,3,6,9] → [4,7,2,9,6,3,1]
目标复杂度： 时间 O(n)，额外空间 O(h)
查看参考答案
解题思路： 交换当前节点左右引用，再递归处理两个子树。
不变量： 递归返回时当前子树的每个节点都已交换左右孩子。
public static class AlgCode057Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static TreeNode? Solve(TreeNode? root)
{
if (root is null) return null;
(root.Left, root.Right) = (Solve(root.Right), Solve(root.Left));
return root;
}
}复杂度： 时间 O(n)，递归栈 O(h)。
边界用例： 空树；单节点；退化链形树。
面试追问：
- 如何用队列实现迭代翻转？
058 在线性时间内判断二叉树是否高度平衡。
难度： 进阶
方法签名： TreeNode? root
输入约束： 平衡定义为每个节点左右子树高度差不超过 1
示例： [3,9,20,null,null,15,7] → true
目标复杂度： 时间 O(n)，额外空间 O(h)
查看参考答案
解题思路： 后序返回高度，发现不平衡时返回 -1 并向上传播。
不变量： 非负返回值是准确高度，-1 表示子树已经不平衡。
public static class AlgCode058Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static bool Solve(TreeNode? root) => Height(root) >= 0;
private static int Height(TreeNode? node)
{
if (node is null) return 0;
int left = Height(node.Left);
if (left < 0) return -1;
int right = Height(node.Right);
if (right < 0 || Math.Abs(left - right) > 1) return -1;
return Math.Max(left, right) + 1;
}
}复杂度： 时间 O(n)，递归栈 O(h)。
边界用例： 空树；只在根平衡但子树不平衡；退化链形树。
面试追问：
- 重复调用最大深度为什么会退化为 O(n²)？
059 返回普通二叉树中两个已存在节点的最近公共祖先。
难度： 进阶
方法签名： TreeNode root, TreeNode first, TreeNode second
输入约束： 两个目标节点均存在且按引用识别
示例： 根 3，目标 5 和 1 → 节点 3
目标复杂度： 时间 O(n)，额外空间 O(h)
查看参考答案
解题思路： 当前节点命中即返回；左右子树都返回非空时当前节点是最近公共祖先。
不变量： 递归返回值表示当前子树中找到的目标或已经确定的祖先。
public static class AlgCode059Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public static TreeNode? Solve(
TreeNode? root,
TreeNode first,
TreeNode second)
{
if (root is null ||
ReferenceEquals(root, first) ||
ReferenceEquals(root, second))
return root;
TreeNode? left = Solve(root.Left, first, second);
TreeNode? right = Solve(root.Right, first, second);
if (left is not null && right is not null) return root;
return left ?? right;
}
}复杂度： 时间 O(n)，递归栈 O(h)。
边界用例： 一个目标是另一个祖先；目标分居两侧；按引用而非值比较。
面试追问：
- 如果树是 BST，如何利用有序性降低搜索范围？
060 实现可往返还原任意二叉树的序列化与反序列化。
难度： 综合
方法签名： TreeCodec Create()
输入约束： 节点值为 int，格式需要保留 null 结构
示例： [1,2,3,null,null,4,5] 序列化后可还原同构树
目标复杂度： 序列化与反序列化均为时间 O(n)、空间 O(n)
查看参考答案
解题思路： 使用前序遍历并为 null 写入 #，反序列化按同一顺序消费标记。
不变量： 每次读取一个标记后，递归准确消费该节点整棵子树的标记。
public static class AlgCode060Solution
{
public sealed class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int value) => Value = value;
}
public sealed class TreeCodec
{
public string Serialize(TreeNode? root)
{
var tokens = new List<string>();
Write(root, tokens);
return string.Join(',', tokens);
}
public TreeNode? Deserialize(string source)
{
string[] tokens = source.Split(',');
int index = 0;
return Read(tokens, ref index);
}
private static void Write(TreeNode? node, List<string> tokens)
{
if (node is null)
{
tokens.Add("#");
return;
}
tokens.Add(node.Value.ToString());
Write(node.Left, tokens);
Write(node.Right, tokens);
}
private static TreeNode? Read(string[] tokens, ref int index)
{
string token = tokens[index++];
if (token == "#") return null;
var node = new TreeNode(int.Parse(token));
node.Left = Read(tokens, ref index);
node.Right = Read(tokens, ref index);
return node;
}
}
public static TreeCodec Solve() => new();
}复杂度： 序列化与反序列化均为时间 O(n)、结果和递归空间 O(n)。
边界用例： 空树；负数；重复值；退化深树；非法格式需另加校验。
面试追问：
- 只给前序值而不记录 null，为什么无法唯一还原普通二叉树？