程序员面试金典 - 面试题 04.09. 二叉搜索树序列(双端队列+回溯)**
程序员文章站
2024-03-04 09:15:35
...
1. 题目
从左向右遍历一个数组,通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。
给定一个由不同节点组成的二叉树,输出所有可能生成此树的数组。
示例:
给定如下二叉树
2
/ \
1 3
返回:
[
[2,1,3],
[2,3,1]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/bst-sequences-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 参考大佬的解法
可能的序列
[[0,1,2,3,4],[0,1,2,4,3],[0,1,3,4,2],[0,1,3,2,4],
[0,1,4,2,3],[0,1,4,3,2],[0,2,1,3,4],[0,2,1,4,3]]
class Solution {
vector<vector<int>> ans;
vector<int> temp;
deque<TreeNode*> q;
public:
vector<vector<int>> BSTSequences(TreeNode* root) {
if(!root)
return {{}};
q.push_back(root);
dfs();
return ans;
}
void dfs()
{
if(q.empty())
{
ans.push_back(temp);
return;
}
int size = q.size();
while(size--)//这层有几个人
{
TreeNode *tp = q.front();
q.pop_front(); //队列,第一个人出队
temp.push_back(tp->val);
int children = 0;
if(tp->left)//把下层加入队列
{
q.push_back(tp->left);
children++;
}
if(tp->right)
{
q.push_back(tp->right);
children++;
}
dfs();
while(children--)
q.pop_back();//把下层的删除
q.push_back(tp);//第一个人去队尾
temp.pop_back();
}
}
};