給出一個BST節點的所有序列，找到根目錄開始節點，將基本上給出相同的二叉搜索樹的所有序列。給定一個BST和其根，打印其產生相同的BST
給定一個BST，說
3
/\
1 5
答案應該是3,1,5和3,5,1。
另一示例
5
/ \
4 7
/ /\
1 6 10
的輸出將是
5,4,1,7,6,10
5,4,7,6,10,1
5,7,6,10,4,1
etc
然而，這裏的不變性是父母的索引必須總是小於其子女。我很難實現它。
我想，你希望這將產生相同的BST所有序列的列表。
在這個回答中，我們將使用分而治之。
我們將創建一個函數findAllSequences(Node *ptr)，它將一個節點指針作爲輸入並返回所有將生成從ptr掛起的子樹的不同序列。該函數將返回一個int向量矢量，即包含所有序列的vector<vector<int>>。
的主要思想生成序列是根必須將其所有的孩子面前。
算法：
基本案例1：
如果ptr是NULL，則返回一個向量中的空序列。
if (ptr == NULL) {
vector<int> seq;
vector<vector<int> > v;
v.push_back(seq);
return v;
}
基本案例2：
如果ptr是leaf node，然後返回與單個序列的載體。它的平凡性，這個序列將只包含一個元素，即該節點的值。
if (ptr -> left == NULL && ptr -> right == NULL) {
vector<int> seq;
seq.push_back(ptr -> val);
vector<vector<int> > v;
v.push_back(seq);
return v;
}
鴻溝部分（這部分是非常簡單的。）
我們假設我們有一個可以解決這個問題的功能，因此，我們解決它的左子樹和右子樹。
vector<vector<int> > leftSeq = findAllSeq(ptr -> left);
vector<vector<int> > rightSeq = findAllSeq(ptr -> right);
合併兩種溶液（的癥結是在此步驟。）
直到現在我們有兩個組方含不同序列：
i. leftSeq - all sequences in this set will generate left subtree.
ii. rightSeq - all sequences in this set will generate right subtree.
現在在左子樹中的每個步驟都可以右子樹的每個序列進行合併。在合併時，我們應該小心地保留元素的相對順序。同樣在每一個合併序列中，我們都會在開始時添加當前節點的值，因爲根必須在所有子節點之前出現。
僞用於合併
vector<vector<int> > results
for all sequences L in leftSeq
for all sequences R in rightSeq
create a vector flags with l.size() 0's and R.size() 1's
for all permutations of flag
generate the corresponding merged sequence.
append the current node's value in beginning
add this sequence to the results.
return results.
說明：讓我們以一個序列，說從集leftSeq，和序列L(of size n)，說從設置rightSeqR(of size m)。
現在這兩個序列可以合併在m + n C n方法！
證明：合併後，新序列將有m + n元素。因爲我們必須保持元素的相對順序，所以首先我們將填充所有n中的L的元素在n中的任意一個地方，共(m+n)個地點。剩餘的m之後可以填入R的元素。因此我們必須choose n places from (m+n) places。
要做到這一點，讓我們創建一個帶布爾向量，說flags與n0's和m的01's .A值表示從left序列的成員，並1值代表成員來自right序列填充它。剩下的就是產生這個標誌矢量的所有permutations，這可以用next_permutation完成。現在對於標誌的每個排列，我們將有一個明確的合併序列L和R。
例如：說L = {1，2，3} R = {4,5}
所以，n=3和m=2
因此，我們可以有3 + 2ç合併序列，即10.
1.now，最初flags = {0 0 0 1 }，填充有 0's和 1's
這將導致到該合併的序列：1 2 3 4 5
2.after主叫nextPermutation我們將有
flags = {0 0 1 }
，這將產生序列：1 2 4 3 5
3 。調用nextPermutation後再次，我們將有
flags = {0 0 0}
ANS這將產生序列：1 2 4 5 3
等 ...
代碼在C++
vector<vector<int> > findAllSeq(TreeNode *ptr)
{
if (ptr == NULL) {
vector<int> seq;
vector<vector<int> > v;
v.push_back(seq);
return v;
}
if (ptr -> left == NULL && ptr -> right == NULL) {
vector<int> seq;
seq.push_back(ptr -> val);
vector<vector<int> > v;
v.push_back(seq);
return v;
}
vector<vector<int> > results, left, right;
left = findAllSeq(ptr -> left);
right = findAllSeq(ptr -> right);
int size = left[0].size() + right[0].size() + 1;
vector<bool> flags(left[0].size(), 0);
for (int k = 0; k < right[0].size(); k++)
flags.push_back(1);
for (int i = 0; i < left.size(); i++) {
for (int j = 0; j < right.size(); j++) {
do {
vector<int> tmp(size);
tmp[0] = ptr -> val;
int l = 0, r = 0;
for (int k = 0; k < flags.size(); k++) {
tmp[k+1] = (flags[k]) ? right[j][r++] : left[i][l++];
}
results.push_back(tmp);
} while (next_permutation(flags.begin(), flags.end()));
}
}
return results;
}
更新2017年3月3日：此解決方案將不會如果原始樹包含重複項，則完美工作。
好吧，這裏是我的Python代碼，它產生的所有序列的元素/數字相同的BST。 對於邏輯我提到的書破解Gayle Laakmann編碼採訪Mcdowell
from binarytree import Node, bst, pprint
def wavelist_list(first, second, wave, prefix):
if first:
fl = len(first)
else:
fl = 0
if second:
sl = len(second)
else:
sl = 0
if fl == 0 or sl == 0:
tmp = list()
tmp.extend(prefix)
if first:
tmp.extend(first)
if second:
tmp.extend(second)
wave.append(tmp)
return
if fl:
fitem = first.pop(0)
prefix.append(fitem)
wavelist_list(first, second, wave, prefix)
prefix.pop()
first.insert(0, fitem)
if sl:
fitem = second.pop(0)
prefix.append(fitem)
wavelist_list(first, second, wave, prefix)
prefix.pop()
second.insert(0, fitem)
def allsequences(root):
result = list()
if root == None:
return result
prefix = list()
prefix.append(root.value)
leftseq = allsequences(root.left)
rightseq = allsequences(root.right)
lseq = len(leftseq)
rseq = len(rightseq)
if lseq and rseq:
for i in range(lseq):
for j in range(rseq):
wave = list()
wavelist_list(leftseq[i], rightseq[j], wave, prefix)
for k in range(len(wave)):
result.append(wave[k])
elif lseq:
for i in range(lseq):
wave = list()
wavelist_list(leftseq[i], None, wave, prefix)
for k in range(len(wave)):
result.append(wave[k])
elif rseq:
for j in range(rseq):
wave = list()
wavelist_list(None, rightseq[j], wave, prefix)
for k in range(len(wave)):
result.append(wave[k])
else:
result.append(prefix)
return result
if __name__=="__main__":
n = int(input("what is height of tree?"))
my_bst = bst(n)
pprint(my_bst)
seq = allsequences(my_bst)
print("All sequences")
for i in range(len(seq)):
print("set %d = " %(i+1), end="")
print(seq[i])
example output:
what is height of tree?3
___12
/ \
__ 6 13
/ \ \
0 11 14
\
2
All sequences
set 1 = [12, 6, 0, 2, 11, 13, 14]
set 2 = [12, 6, 0, 2, 13, 11, 14]
set 3 = [12, 6, 0, 2, 13, 14, 11]
set 4 = [12, 6, 0, 13, 2, 11, 14]
set 5 = [12, 6, 0, 13, 2, 14, 11]
set 6 = [12, 6, 0, 13, 14, 2, 11]
set 7 = [12, 6, 13, 0, 2, 11, 14]
set 8 = [12, 6, 13, 0, 2, 14, 11]
set 9 = [12, 6, 13, 0, 14, 2, 11]
set 10 = [12, 6, 13, 14, 0, 2, 11]
set 11 = [12, 13, 6, 0, 2, 11, 14]
set 12 = [12, 13, 6, 0, 2, 14, 11]
set 13 = [12, 13, 6, 0, 14, 2, 11]
set 14 = [12, 13, 6, 14, 0, 2, 11]
set 15 = [12, 13, 14, 6, 0, 2, 11]
set 16 = [12, 6, 0, 11, 2, 13, 14]
set 17 = [12, 6, 0, 11, 13, 2, 14]
set 18 = [12, 6, 0, 11, 13, 14, 2]
set 19 = [12, 6, 0, 13, 11, 2, 14]
set 20 = [12, 6, 0, 13, 11, 14, 2]
set 21 = [12, 6, 0, 13, 14, 11, 2]
set 22 = [12, 6, 13, 0, 11, 2, 14]
set 23 = [12, 6, 13, 0, 11, 14, 2]
set 24 = [12, 6, 13, 0, 14, 11, 2]
set 25 = [12, 6, 13, 14, 0, 11, 2]
set 26 = [12, 13, 6, 0, 11, 2, 14]
set 27 = [12, 13, 6, 0, 11, 14, 2]
set 28 = [12, 13, 6, 0, 14, 11, 2]
set 29 = [12, 13, 6, 14, 0, 11, 2]
set 30 = [12, 13, 14, 6, 0, 11, 2]
set 31 = [12, 6, 11, 0, 2, 13, 14]
set 32 = [12, 6, 11, 0, 13, 2, 14]
set 33 = [12, 6, 11, 0, 13, 14, 2]
set 34 = [12, 6, 11, 13, 0, 2, 14]
set 35 = [12, 6, 11, 13, 0, 14, 2]
set 36 = [12, 6, 11, 13, 14, 0, 2]
set 37 = [12, 6, 13, 11, 0, 2, 14]
set 38 = [12, 6, 13, 11, 0, 14, 2]
set 39 = [12, 6, 13, 11, 14, 0, 2]
set 40 = [12, 6, 13, 14, 11, 0, 2]
set 41 = [12, 13, 6, 11, 0, 2, 14]
set 42 = [12, 13, 6, 11, 0, 14, 2]
set 43 = [12, 13, 6, 11, 14, 0, 2]
set 44 = [12, 13, 6, 14, 11, 0, 2]
set 45 = [12, 13, 14, 6, 11, 0, 2]
對於上面的代碼，我已經使用二叉樹包創建了給定長度的BST。 –
說清楚。你的意思是沒有給定節點的二叉樹表示？ – Dineshkumar