LeetCode 面试题 04.09. 二叉搜索树序列
题目描述
题意分析
依次把一个序列插入空二叉搜索树，要求最终得到给定树的结构和节点值，返回所有这样的序列。节点值互不相同，不能只给出某一种遍历顺序。
解法：回溯选择已满足父节点条件的候选
核心思路
[!blue]
插入序列的第一个节点一定成为根。对任意子树也是如此：它的根必须先于自己的后代出现，否则较早插入的后代就会占据这个根的位置。因此合法序列必须满足每个父节点都排在孩子之前。
这个条件也足够。根先插入后，左子树的值都会被分到左边，右子树的值都会被分到右边，两边的插入顺序可以任意交错；在每棵子树内部继续保证根先于后代，就会递归构造出原来的结构。于是本题转化为枚举满足父子先后约束的全部序列。
用
path保存已经选择的前缀，用candidates保存父节点已经选中、但自己还未选中的节点。开始只有根可选。每一步任选一个候选加入path，把它从候选中移除，再加入它的非空孩子；孩子的唯一前置条件刚刚满足，因此正好成为新的候选。每个合法序列的下一项都必须在当前候选中，而候选中的每一项都可以合法地接在当前前缀后面。逐个尝试全部候选就不会遗漏；节点值互异，不同选择产生不同前缀，也不会重复输出同一序列。候选为空时，全部节点都已选择，保存当前路径的一份副本。
Java 复用同一候选列表：递归返回后先移除本轮追加的孩子，再弹出路径末项，最后把选中节点放回原下标，恢复下一分支的起点。Go 为每个分支复制候选切片，所以只需回退共享的
path。两种实现都必须复制完整路径后再存入答案，避免后续回溯修改已保存结果。
解题步骤
- 空树返回包含一个空序列的结果。
- 初始只有根可选。
- 每层固定当前候选数，尝试移除一个候选并追加到路径，再加入它的孩子。
- 递归返回后恢复路径与候选集合；没有候选时复制完整路径。
空树对应一个合法的空插入序列，所以结果外层有一项，而这一项长度为 0。返回空的外层数组会错误表示没有任何合法序列。
代码实现
class Solution {
public List<List<Integer>> BSTSequences(TreeNode root) {
List<List<Integer>> answer = new ArrayList<>();
if (root == null) {
answer.add(new ArrayList<>());
return answer;
}
List<TreeNode> candidates = new ArrayList<>();
candidates.add(root);
backtrack(candidates, new ArrayList<>(), answer);
return answer;
}
private void backtrack(
List<TreeNode> candidates, List<Integer> path, List<List<Integer>> answer) {
if (candidates.isEmpty()) {
answer.add(new ArrayList<>(path));
return;
}
// size 先固定，避免循环中新追加的孩子在本层被重复枚举。
int size = candidates.size();
for (int i = 0; i < size; i++) {
TreeNode node = candidates.remove(i);
path.add(node.val);
int added = 0;
if (node.left != null) {
candidates.add(node.left);
added++;
}
if (node.right != null) {
candidates.add(node.right);
added++;
}
backtrack(candidates, path, answer);
// 逆序撤销：先删孩子，再退 path，最后把节点放回原下标。
for (int j = 0; j < added; j++) {
candidates.remove(candidates.size() - 1);
}
path.remove(path.size() - 1);
candidates.add(i, node);
}
}
}
func BSTSequences(root *TreeNode) [][]int {
if root == nil {
return [][]int{
{},
}
}
answer := make([][]int, 0)
candidates := []*TreeNode{
root,
}
path := make([]int, 0)
var dfs func([]*TreeNode)
dfs = func(candidates []*TreeNode) {
if len(candidates) == 0 {
cur := append([]int(nil), path...)
answer = append(answer, cur)
return
}
size := len(candidates)
for i := 0; i < size; i++ {
node := candidates[i]
// 每层复制一份候选集，天然免去撤销动作。
next := append([]*TreeNode{}, candidates[:i]...)
next = append(next, candidates[i+1:]...)
if node.Left != nil {
next = append(next, node.Left)
}
if node.Right != nil {
next = append(next, node.Right)
}
path = append(path, node.Val)
dfs(next)
path = path[:len(path)-1]
}
}
dfs(candidates)
return answer
}
复杂度分析
- 时间复杂度：设 n 为节点数、S 为答案数。当前数组列表删除/插入或复制需要 O(n)，可给出 O(n²S) 时间上界，输出本身需要 Ω(nS)。
- 空间复杂度：Java 额外空间 O(n)，Go 每层复制候选集合，额外空间最坏 O(n²)；输出另占 O(nS)。
关键点总结
[!green]
候选集合表示当前已经满足前置条件的节点，而不是固定的某一层；选中节点后，它的孩子可以与原有候选交错出现，这正是多种合法 BST 插入顺序的来源。
易错点总结
[!yellow]
- 只排列左右子树整体顺序会漏掉两边交错的情况。
- Java 撤销时先删本轮新增孩子，再恢复被移除节点的原下标。
- 保存答案必须复制路径。
- 空树是一个空序列，不是零种序列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 46. 全排列 | 中等 | 同样逐个选择并回溯，但本题下一项只能来自父节点已选的候选集合。 |
| 210. 课程表 II | 中等 | 同样满足前置依赖，原题只需一个拓扑顺序，本题枚举树形依赖的全部合法顺序。 |