1. 題目

從左向右遍歷一個(gè)數(shù)組，通過(guò)不斷將其中的元素插入樹(shù)中可以逐步地生成一棵二叉搜索樹(shù)。
給定一個(gè)由不同節(jié)點(diǎn)組成的二叉樹(shù)，輸出所有可能生成此樹(shù)的數(shù)組。

示例: 給定如下二叉樹(shù)2/ \1 3 返回:[[2,1,3],[2,3,1] ]

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/bst-sequences-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類似題目：
LeetCode 95. 不同的二叉搜索樹(shù) II（遞歸）
LeetCode 96. 不同的二叉搜索樹(shù)（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--)//這層有幾個(gè)人{TreeNode *tp = q.front();q.pop_front(); //隊(duì)列，第一個(gè)人出隊(duì)temp.push_back(tp->val);int children = 0;if(tp->left)//把下層加入隊(duì)列{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);//第一個(gè)人去隊(duì)尾temp.pop_back();}} };

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 04.09. 二叉搜索树序列（双端队列+回溯）**的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。