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

Faye ·

更新时间:2024-09-20

· 821 次阅读

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> ans;
	vector temp;
	deque q;
public:
    vector<vector> 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();
    	}
    }
};

作者：Michael阿明

面试题双端队列面试队列程序二叉搜索树程序员