力扣面试题04.09：二叉搜索树序列生成算法

一、问题背景

二叉搜索树(BST)的构建可以有多种插入顺序，题目要求找出所有能生成相同BST的插入序列。

二、核心算法解析

1. ‌回溯算法‌：系统地枚举所有可能的插入顺序

2. ‌候选集管理‌：维护当前可插入的节点集合

3. ‌递归实现‌：深度优先搜索所有可能的路径

三、关键实现细节

1. ‌候选集选择‌：使用双端队列(deque)高效管理候选节点

2. ‌回溯操作‌：每次递归调用后恢复状态

3. ‌终止条件‌：当没有候选节点时记录当前路径

四、代码实现

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();
        }
    }
};