力扣面试04.09题解析：生成二叉搜索树的所有序列
一、题目解读
力扣面试04.09题要求生成一棵给定二叉搜索树（BST）的所有可能序列。由于BST中序遍历结果唯一，但节点插入顺序不同可能导致不同树结构，因此需通过深度遍历所有节点组合，输出所有合法的BST序列。题目难点在于如何高效且无重复地生成所有序列，并确保每个序列对应有效的BST结构。
二、解题思路
1. 队列初始化：将根节点入队，作为初始候选节点集。
2. 递归回溯：每次从队列头部取出节点，记录其值，并递归处理其左右子树。
3. 子节点入队：若当前节点有左/右子节点，将其加入队列末尾，扩展候选集。
4. 回溯撤销：递归结束后，需回溯撤销子节点入队操作，恢复当前节点状态，继续遍历其他路径。
5. 结果收集：当队列为空时，当前路径代表一棵完整BST的序列，加入结果集。
三、解题步骤
1. 初始化：若根节点为空，直接返回空结果集。
2. 创建队列：将根节点加入候选队列。
3. 主循环：
○ 循环直至队列为空，每次处理一个节点：
取出当前节点，记录值到路径。
若存在左/右子节点，分别入队（扩展搜索空间）。
递归调用 backtrack()，生成子树序列。
回溯时弹出子节点，恢复队列状态（避免重复）。
○ 最终路径加入结果集。
4. 返回所有序列：完成所有路径搜索后，返回结果集。
四、代码与注释
class Solution {
public:
vector<vector<int>> BSTSequences(TreeNode* root) {
if (!root) return {{}}; // 空树特判
vector<vector<int>> res; // 结果集
vector<int> path; // 当前路径
deque<TreeNode*> candidates; // 候选节点队列
candidates.push_back(root); // 根节点入队
backtrack(candidates, path, res); // 启动回溯
return res;
}
void backtrack(deque<TreeNode*>& candidates, vector<int>& path, vector<vector<int>>& res) {
if (candidates.empty()) { // 队列为空，路径完整
res.push_back(path); // 加入结果集
return;
}
int size = candidates.size(); // 记录当前队列长度
for (int i = 0; i < size; ++i) {
TreeNode* curr = candidates.front(); // 取出当前节点
candidates.pop_front(); // 从队列移除
path.push_back(curr->val); // 记录节点值
// 将子节点加入候选集（扩展搜索空间）
if (curr->left) candidates.push_back(curr->left);
if (curr->right) candidates.push_back(curr->right);
backtrack(candidates, path, res); // 递归生成子树序列
// 回溯：撤销子节点入队，恢复状态
if (curr->right) candidates.pop_back();
if (curr->left) candidates.pop_back();
candidates.push_back(curr); // 回溯至父节点
path.pop_back(); // 撤销路径值
}
}
};注释说明：
● 使用 deque 队列动态管理候选节点，支持高效头尾操作。
● size 提前记录队列长度，避免循环中动态计算影响效率。
● 回溯时通过 pop_back() 撤销子节点，确保不重复遍历。
五、总结
1. 算法优势：回溯算法天然适合路径搜索问题，通过队列管理候选节点，避免深度递归栈溢出风险。
2. 优化方向：若题目允许去重或剪枝，可进一步优化时间复杂度，但原解法已满足面试需求。
3. 应用场景：适用于需要生成所有组合、排列的树结构问题，如力扣其他序列化/构造类题目。
原创内容 转载请注明出处
