欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

程序员面试金典 - 面试题 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. 解题

程序员面试金典 - 面试题 04.09. 二叉搜索树序列(双端队列+回溯)**

可能的序列
[[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();
    	}
    }
};