给定BST及其根，打印产生相同bst的所有节点序列-Java 学习之路

给定BST，找到从root开始的所有节点序列，它们基本上会给出相同的二叉搜索树 .

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

等等

然而，这里的不变量是父母的索引必须始终小于其子项 . 我很难实现它 .

2 回答

13
我假设你想要一个生成相同BST的所有序列的列表 .
在这个答案中，我们将使用 Divide and Conquer .
我们将创建一个函数 findAllSequences(Node *ptr) ，它将一个节点指针作为输入，并返回所有不同的序列，这些序列将生成从 ptr 挂起的子树 . 此函数将返回Vector of Vector of int，即包含所有序列的 vector<vector<int>> .

生成序列的主要思想是 root must come before all its children .

算法：

Base Case 1:
如果 ptr 是 NULL ，则返回一个空序列的向量 .
```
if (ptr == NULL) {
    vector<int> seq;
    vector<vector<int> > v;
    v.push_back(seq);
    return v;
}
```
Base Case 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;
}
```
Divide Part （这部分非常简单 . ）
我们假设我们有一个可以解决这个问题的函数，因此我们为左子树和右子树解决它 .
```
vector<vector<int> > leftSeq  = findAllSeq(ptr -> left);
vector<vector<int> > rightSeq = findAllSeq(ptr -> right);
```
Merging the two solutions . （关键在于此步骤 . ）
到目前为止，我们有两套不同的序列：
```
i. leftSeq  - all sequences in this set will generate left subtree.
ii. rightSeq - all sequences in this set will generate right subtree.
```
现在左子树中的每个序列可以与右子树的每个序列合并 . 在合并时，我们应该注意保留元素的相对顺序 . 同样在每个合并序列中，我们将在开始时添加当前节点的值beacuse root必须在所有子节点之前 .

Merge的伪代码
```
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.
```
Explanation ：让我们从集合 leftSeq 中取一个序列，例如 L(of size n) ，然后从集合 rightSeq 中取一个序列，例如 R(of size m) .
现在这两个序列可以以 m+nCn 方式合并！
Proof ：合并后，新序列将包含 m + n 个元素 . 由于我们必须保持元素的相对顺序，所以首先我们将在 n 个位置的 n 中填充 L 中的所有元素 . 之后 m 个地方可以填充 R 的元素 . 因此我们必须 choose n places from (m+n) places .
为此，让我们创建一个布尔向量，比如说 flags 并用 n 0's 和 m 1's 填充它 . 0 的值表示来自 left 序列的成员，值 1 表示来自 right 序列的成员 . 剩下的就是生成所有 permutations 这个标志向量，这可以用 next_permutation 来完成 . 现在，对于每个标志的排列，我们将有一个明确的合并序列 L 和 R .
eg: 说 L = {1,2,3} R = {4,5}
所以， n=3 和 m=2
因此，我们可以有 3+2C3 合并序列，即10 .
1.now，最初 flags = {0 0 0 1 1}，填充 3 0's 和 2 1's
这将导致这个合并的序列： 1 2 3 4 5
2.在调用nextPermutation后我们会有
flags = {0 0 1 0 1}
这将生成序列： 1 2 4 3 5
3.在调用nextPermutation之后我们会有
flags = {0 0 1 1 0}
这将生成序列： 1 2 4 5 3
等等...

Code in 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;
}
```
Update 3rd March 2017: 如果原始树包含重复项，此解决方案将无法正常工作 .
回复于 2024-05-03T22:52:31+08:00

这里是我的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]

回复于 2024-05-03T22:52:31+08:00

给定BST及其根，打印产生相同bst的所有节点序列

2 回答

相关问题