给出一个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