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

19339201706

一、问题背景

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

二、核心算法解析

• ‌回溯算法‌：系统地枚举所有可能的插入顺序
• ‌候选集管理‌：维护当前可插入的节点集合
• ‌递归实现‌：深度优先搜索所有可能的路径
  
  

三、关键实现细节

• ‌候选集选择‌：使用双端队列(deque)高效管理候选节点
• ‌回溯操作‌：每次递归调用后恢复状态
• ‌终止条件‌：当没有候选节点时记录当前路径
  
  

四、代码实现

1. class Solution {
   
2. public:
   
3.     vector<vector<int>> BSTSequences(TreeNode* root) {
   
4.         if (!root) return {{}};
   
5.         vector<vector<int>> res;
   
6.         vector<int> path;
   
7.         deque<TreeNode*> candidates;
   
8.         candidates.push_back(root);
   
9.         backtrack(candidates, path, res);
   
10.         return res;
    
11.     }
    
12.     void backtrack(deque<TreeNode*>& candidates, vector<int>& path, vector<vector<int>>& res) {
    
13.         if (candidates.empty()) {
    
14.             res.push_back(path);
    
15.             return;
    
16.         }
    
17.       
    
18.         int size = candidates.size();
    
19.         for (int i = 0; i < size; ++i) {
    
20.             TreeNode* curr = candidates.front();
    
21.             candidates.pop_front();
    
22.             path.push_back(curr->val);
    
23.            
    
24.             // 将子节点加入候选集
    
25.             if (curr->left) candidates.push_back(curr->left);
    
26.             if (curr->right) candidates.push_back(curr->right);
    
27.            
    
28.             backtrack(candidates, path, res);
    
29.            
    
30.             // 回溯
    
31.             if (curr->right) candidates.pop_back();
    
32.             if (curr->left) candidates.pop_back();
    
33.             candidates.push_back(curr);
    
34.             path.pop_back();
    
35.         }
    
36.     }
    
37. };

复制代码

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