专栏首页Michael阿明学习之路程序员面试金典 - 面试题 04.09. 二叉搜索树序列(双端队列+回溯)**

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

1. 题目

从左向右遍历一个数组,通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。 给定一个由不同节点组成的二叉树,输出所有可能生成此树的数组。

示例:
给定如下二叉树

        2
       / \
      1   3
返回:

[
   [2,1,3],
   [2,3,1]
]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/bst-sequences-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

类似题目: LeetCode 95. 不同的二叉搜索树 II(递归) LeetCode 96. 不同的二叉搜索树(DP)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1390. 四因数

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/four-divisors 著作权归领扣网络所有。商...

    Michael阿明
  • LeetCode 2020 力扣杯全国春季编程大赛(1644/4093,前40.2%)

    前两题比较顺利,24分钟做出来了,第3,4两题试了好久,都显示超时,第5题没心思看,想着第3,4题应该能做出来的。

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • C++ 对vector进行排序

    title: C++ vector排序 tags: c++,vector,排序 grammar_cjkRuby: true --- 每次都要重复造轮子真...

    marsggbo
  • 洛谷P3809 【模板】后缀排序

    题目背景 这是一道模板题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

    attack
  • BZOJ4698: Sdoi2008 Sandy的卡片(后缀数组 二分)

    attack
  • 第88场周赛

    第二反应:根据上述这个模拟超时过程,想一优化,shifts数组后面开始,逐个偏移,根据描述,后面的偏移会加到前面。于是有了后缀和这一说法。

    用户1145562
  • HPU personal-training 2

    A - Kefa and Park 题意:就是一棵树,然后本人的家在根上,餐厅在叶子节点上。然后在前往叶子结点的餐厅的时候,途中的结点上有猫,而这个人特别怕...

    杨鹏伟
  • AtCoder Beginner Contest 181 A ~ E

    D.题意:就是给你一个字符串,让你判断其不同排序是否为能够整除8。能的话就输出“Yes”,否则就输出“No”。

    杨鹏伟
  • LeetCode题解-Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    卡尔曼和玻尔兹曼谁曼

扫码关注云+社区

领取腾讯云代金券