力扣面试题04.09:二叉搜索树序列生成算法
一、问题背景
二叉搜索树(BST)的构建可以有多种插入顺序,题目要求找出所有能生成相同BST的插入序列。
二、核心算法解析
三、关键实现细节
四、代码实现
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(); } } };
原创内容 转载请注明出处