1. 题目
从左向右遍历一个数组,通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。
给定一个由不同节点组成的二叉树,输出所有可能生成此树的数组。
示例:给定如下二叉树2/ \1 3返回:[[2,1,3],[2,3,1]]
来源:力扣(LeetCode)
链接:https://leetcode-/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();}}};