BST Sequences
A binary search tree was created by traversing through an array from left to right and inserting each element. Given a binary search tree with distinct elements, print all possible arrays that could have led to this tree.
EXAMPLE
Input: 2
/ \
1 3
Output: {2, 1, 3}, {2, 3, 1}
Solution
要细看 CC
Complexity
Code
ArrayList<LinkedLIst<Integer>> allSequences(TreeNode node) {
ArrayLIst<LinkedList<Integer>> result = new ArrayList<LinkedList<Integer>>();
if (node == null){
result.add(new LinkedList<Integer>());
return result;
}
LinkedList<Integer> prefix = new LinkedList<Integer>();
prefix.add(node.data);
ArrayList<LinkedLIst<Integer>> leftSeq = allSequences(node.left);
ArrayList<LinkedList<Integer>> rightSeq = allSequences(node.right);
// weave
for (LinkedList<Integer> left : leftSeq) {
for (LinkedList<Integer> right : rightSeq) {
ArrayList<LinkedList<Integer>> weaved = new ArrayList<LinkedList<Integer>>();
weaveLists(left, right, weaved, prefix);
result.addAll(weaved);
}
}
return result;
}
void weaveLists(LinkedList<Integer> first, LinkedList<Integer> second,
ArrayList<LinkedList<Integer>> results, LinkedList<Integer> prefix) {
// one list is empty. Add remainder to [a cloned] prefix and store result.
if (first.size() == 0 || second.size() == 0){
LinkedList<Integer> result = (LinkedList<Integer>) prefix.clone();
result.addAll(first);
result.addAll(second);
results.add(result);
return ;
}
// Recurse with head of first added to the prefix. Removing the head will
// damage first, so we'll need to put it back where we found it afterwards.
int headFirst = first.removeFirst();
prefix.addLast(headFirst);
weaveLists(first, second, results, prefix);
prefix.removeLast();
first.addFirst(headFirst);
// Do the same thing with second, damaging and then restoring the list
int headSecond = second.removeFirst();
prefix.addLast(headSecond);
weaveLists(first, second, results, prefix);
prefix.removeLast();
second.addFirst(headSecond);
}