当前位置:首页 > 力扣题解 > 力扣面试题04.09:二叉搜索树序列生成算法

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

2周前 (06-20)力扣题解87

截图未命名.jpg 力扣面试题04.09:二叉搜索树序列生成算法 二叉搜索树 回溯算法 力扣面试题 C++实现 树结构遍历 第1张

一、问题背景

二叉搜索树(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();
        }
    }
};


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。