LeetCode 面试题 04.09. 二叉搜索树序列

2026-03-28 HGNULB 约 10 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 面试题 04.09. 二叉搜索树序列

题意分析

给一棵二叉搜索树，反推出所有可能的插入序列：把这些数字按该序列依次插入一棵空树，得到的形状必须与给定的树完全一致。要返回全部这样的序列。

关键在于「插入」这个动作的性质：往二叉搜索树里插一个值时，它会沿着比较路径一直走到某个空位挂上去，落点由已有节点唯一决定。因此一个节点能被插入，当且仅当它的父节点已经先被插入——否则它就会挂到别的位置去，形状对不上。

反过来说，只要父节点先于孩子出现，序列就一定能还原出这棵树；至于兄弟之间、堂兄弟之间谁先谁后，完全自由。于是题意被翻译成一句纯粹的组合语言：求这棵树按父子偏序的所有拓扑序。根必然排在第一位。

约束还透露了规模信号：答案数量本身是指数级的，题目要求全部列出，说明不存在多项式解法，必须穷举；能做的只是保证「每一步扩展都必然通向一个合法答案」，不做无效尝试。

边界：空树对应唯一的空序列，返回的是含一个空列表的结果，而不是空结果；单节点树只有一种序列；节点值互异，无需考虑去重。

解法：回溯搜索

核心思路

最容易想到的暴力是枚举全部 n! 种排列，逐条模拟插入再比对树形。它一定对，但绝大多数排列在第一步就废了，验证成本还是 $O(n)$ 一条，浪费得离谱。瓶颈在于「先生成再验证」——合法性其实可以在生成过程中就保证。

观察合法序列的生成过程：任何时刻，下一个能写下的节点必须满足「父节点已写、自己未写」。把所有满足这个条件的节点收成一个集合，称作候选集，那么每一步就是「从候选集里任选一个写下」。选完之后，这个节点从候选集移出，它的非空孩子因为父节点刚刚就位而变得可选，加入候选集。

于是状态被压成两样东西：path 是已经写下的序列前缀，candidates 是当前可写的节点集合。搜索的不变量是「path 始终是一个合法前缀（每个节点的父亲都已在 path 中），且 candidates 恰好是所有父已就位、自身未就位的节点」。这条不变量保证了每一条搜索路径都必然走到一个完整的合法答案，没有任何回头验证。

递归的终止条件是候选集为空：此时再没有可写的节点，说明整棵树都已写完，path 就是一条答案。初始候选集只有根，对应「根必须第一个插入」。

回溯的恢复动作要与做出的修改一一对应：写下节点时从候选集删掉它、追加它的孩子、把值压入 path，撤销时就要弹出 path、删掉刚追加的孩子、把节点放回候选集的原位置——放回原位是为了不打乱同层循环的枚举下标。

解题步骤

处理空树：root 为空时直接返回含一个空列表的结果。这不是可有可无的特判，题目对空树的期望输出就是一条空序列。

初始化候选集：只放根节点。这一步把「根必须最先插入」编码进了初始状态，主循环里不再需要任何关于根的特殊处理。

递归终止：候选集为空时把 path 拷贝一份存入答案。必须拷贝——path 是全程复用的可变列表，直接存引用会让所有答案在回溯后变成同一个空列表。

枚举本层选择：先把 size 记下来再循环。循环体内会往候选集尾部追加孩子，若用实时长度当上界，刚加进去的孩子会在同一层被重复枚举，导致同一节点在一条序列里出现多次。

做选择：从候选集第 i 位取出节点并移除，把值压入 path，再把它的非空孩子追加到候选集尾部，同时记下追加了几个。

撤销选择：按与做选择相反的顺序恢复——先从尾部删掉刚追加的 added 个孩子，再弹出 path 末尾，最后把节点插回下标 i。插回原下标而不是尾部，才能保证下一轮 i + 1 指向的仍是原来那个候选节点。

以三节点树 root = 2、左孩子 1、右孩子 3 走一遍。初始 candidates = [2]、path = []。

第一层只有一个选择：取出 2，path = [2]，追加孩子 1 和 3，candidates = [1, 3]。

第二层 size = 2，先试 i = 0 取出 1：path = [2, 1]，1 无孩子，candidates = [3]。第三层只剩一个选择，取出 3 得 path = [2, 1, 3]，候选集空，记下第一条答案。回溯：3 放回，path 退回 [2, 1]；再回溯：1 放回下标 0，candidates 恢复成 [1, 3]，path 退回 [2]。

第二层继续试 i = 1 取出 3：path = [2, 3]，candidates = [1]；取出 1 得 path = [2, 3, 1]，记下第二条答案。回溯到底，candidates 恢复成 [2]。

最终答案是 [[2, 1, 3], [2, 3, 1]]。可以验证：两条序列插进空树都得到根 2、左 1、右 3；而 [1, 2, 3] 之所以不在答案里，正是因为 1 的父节点 2 还没就位，它在候选集里根本不会被提前选中。

代码实现

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
}

复杂度分析

时间复杂度：$O(n \cdot S)$ 级别，n 为节点数、S 为答案条数。搜索树的每一条根到叶路径恰好对应一条答案且不含无效分支，每条答案的收集要拷贝长度 n 的序列；Java 版在候选集中间做删除与插入、Go 版每层复制候选集，都会再带上一个 n 的常数因子。S 本身是指数级的（完全二叉树时增长极快），这是题目要求全量输出所决定的下界。

空间复杂度：$O(n)$（不计答案本身）。递归深度等于节点数，path 与候选集的长度都不超过 n；Go 版每层持有一份候选集副本，栈上合计为 $O(n^2)$。答案数组本身另占 $O(n \cdot S)$。

关键点总结

看到「哪些序列能重建出这个结构」，先把结构约束翻译成偏序关系——本题就是父先于子，问题随即变成求所有拓扑序，这一步转化是难度的全部所在。

「候选集」这个状态设计是通用的：任何「前驱就绪才可选」的枚举问题（拓扑排序计数、任务调度全排列）都可以用同一套框架，选中即出集、并把因它就绪的后继入集。

让每条搜索路径都必然通向合法答案，比「生成后验证」高效一个量级；面试里能说清「为什么不需要回头检查合法性」，比写对代码更能体现功力。

回溯的撤销必须与做选择严格逆序，且节点要放回原下标；这类「集合型状态」的恢复比常见的布尔标记数组更易写错，是本题的主要实现难点。

用固定的 size 而不是实时长度当循环上界，是回溯中「边遍历边修改容器」的标准防御手段。

面试中若时间紧张，可以主动提出 Go 版那种「每层复制候选集」的写法：牺牲一点空间换来完全不用写撤销逻辑，思路更容易讲清楚。

易错点总结

循环上界用实时长度：三节点树 [2, 1, 3] → 取出 2 后候选集变成 [1, 3]，i 还会继续枚举到新加入的孩子，产生 [2, 1, 1] 这类重复节点的非法序列。

把 path 直接存入答案不拷贝：任意树 → 回溯把 path 清空后，答案里所有条目指向同一个已被清空的列表，输出全是空序列。

撤销时把节点追加到候选集尾部而不是插回下标 i：[2, 1, 3] → 第二层第一次迭代后候选集从 [1, 3] 变成 [3, 1]，i = 1 取到的是 1 而不是 3，漏掉 [2, 3, 1] 这条答案。

忘记删除本轮追加的孩子：[2, 1, 3] → 回到上层时候选集里残留着 1 的孩子（若有），下一轮会把不该可选的节点当成候选，生成父子倒序的非法序列。

撤销顺序写成「先放回节点再删孩子」：删除时按尾部下标操作，节点已被插回中间，candidates.size() - 1 删掉的是错误元素，候选集被破坏。

空树返回空结果：root = null → 期望输出是含一个空序列的结果，返回空数组会被判错。

初始候选集放根的两个孩子：[2, 1, 3] → 序列里根本没有根，所有答案长度都少一。

只按层序或前序枚举一种顺序：[2, 1, 3] → 只得到 [2, 1, 3] 一条，漏掉兄弟互换产生的另一条，本质是把「任选一个候选」写成了「固定选第一个」。

Go 版复制候选集时写成 next := candidates[:i] 之类的切片再 append：底层数组被共享，后续 append 会覆盖兄弟分支正在使用的元素，不同分支互相污染，答案随机出错。

用值去重：本题节点值互异，若照搬全排列 II 的同层去重条件，会把结构不同但值相同的合法分支误剪掉。

相似题目

题目	难度	考察点
46. 全排列	中等	候选集恒为「所有未使用元素」，没有偏序约束，是本题的退化情形
47. 全排列 II	中等	元素可重，需排序后加同层去重条件，考点在剪枝而非候选集维护
面试题 08.04. 幂集	中等	每个元素只有选与不选两种决策，搜索树是定深二叉而非可变分支数
面试题 08.07. 无重复字符串的排列组合	中等	用布尔标记数组代替候选集，适合候选恒定不变的场景
108. 将有序数组转换为二叉搜索树	简单	反方向的题：由序列造树，靠取中点保证平衡
剑指 Offer 38. 字符串的排列	中等	与 47 同题，输出去重后的字符串数组
面试题 04.08. 首个共同祖先	中等	同样吃透父子关系，但只需一趟后序合并，不涉及枚举