Given a BST and its root, print all sequences of n

问题:

Given a BST, find all sequences of nodes starting from root that will essentially give the same binary search tree.

Given a bst, say

  3
 /  \
1    5

the answer should be 3,1,5 and 3,5,1.

another example

       5
     /   \
    4     7
   /     / \
  1     6   10

the outputs will be

5,4,1,7,6,10

5,4,7,6,10,1

5,7,6,10,4,1

etc

The invariant here however is that the parent's index must always be lesser than its children. I am having difficulty implementing it.

回答1:

I assume you want a list of all sequences which will generate the same BST.
In this answer, we will use Divide and Conquer.
We will create a function findAllSequences(Node *ptr) which takes a node pointer as input and returns all the distinct sequences which will generate the subtree hanging from ptr. This function will return a Vector of Vector of int, i.e. vector<vector<int>> containing all the sequences.

The main idea for generating sequence is that root must come before all its children.

Algorithm:

Base Case 1:
If ptr is NULL, then return a vector with an empty sequence.

if (ptr == NULL) {
    vector<int> seq;
    vector<vector<int> > v;
    v.push_back(seq);
    return v;
}

Base Case 2:
If ptr is a leaf node, then return a vector with a single sequence. Its Trivial that this sequence will contain only a single element, i.e. value of that 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 (this part is very simple.)
We assume that we have a function that can solve this problem, and thus we solve it for left sub tree and right sub tree.

vector<vector<int> > leftSeq  = findAllSeq(ptr -> left);
vector<vector<int> > rightSeq = findAllSeq(ptr -> right);

Merging the two solutions.(The crux is in this step.)
Till now we have two set containg distinct sequences:

i. leftSeq  - all sequences in this set will generate left subtree.
ii. rightSeq - all sequences in this set will generate right subtree.

Now each sequence in left subtree can be merged with each sequence of right subtree. While merging we should be careful that the relative order of elements is preserved. Also in each of the merged sequence we will add the value of current node in the beginning beacuse root must come before all children.

Pseudocode for 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: Let us take a sequence, say L(of size n) from the set leftSeq, and a sequence, say R(of size m) from set rightSeq.
Now these two sequences can be merged in ^m+nC_n ways!
Proof: After merging, the new sequence will have m + n elements. As we have to maintain the relative order of elements, so firstly we will fill all n the elements from L in any of n places among total (m+n) places. After that remaining m places can be filled by elements of R. Thus we have to choose n places from (m+n) places.
To do this, lets create take a Boolean vector, say flags and fill it with n 0's and m 1's.A value of 0 represents a member from left sequence and a value of 1 represents member from right sequence. All what is left is to generate all permutations of this flags vector, which can be done with next_permutation. Now for each permutation of flags we will have a distinct merged sequence of L and R.
eg: Say L={1, 2, 3} R={4, 5}
so, n=3 and m=2
thus, we can have ³⁺²C₃ merged sequences, i.e. 10.
1.now, Initially flags = {0 0 0 1 1}, filled with 3 0's and 2 1's
this will result into this merged sequence: 1 2 3 4 5
2.after calling nextPermutation we will have
flags = {0 0 1 0 1}
and this will generate sequence: 1 2 4 3 5
3.again after calling nextPermutation we will have
flags = {0 0 1 1 0}
ans this will generate sequence: 1 2 4 5 3
and so on...

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: This solution wont work perfectly if original tree contains duplicates.

回答2:

well here is my python code which does producing all sequences of elements/numbers for same BST. for the logic i referred to the book cracking the coding interview by 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]