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
1
2
3
4
5
|
Input:
2
/ \
1 3
Output: {2, 1, 3}, {2, 3, 1}
|
Hints: #39, #48, #66, #82
解法1
这题不是自己想出来的，具体思路看书。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public List<List<Integer>> allSequences(Node root) {
List<List<Integer>> result = new ArrayList<>();
List<List<Integer>> lefts = allSequences(root.left);
List<List<Integer>> rights = allSequences(root.right);
List<Integer> prefix = new ArrayList<>();
prefix.add(root.value);
for (List<Integer> left : lefts) {
for (List<Integer> right : rights) {
List<List<Integer>> weaveLists = weave(left, right, prefix);
for (List<Integer> weaveList : weaveLists) {
result.add(weaveList.clone());
}
}
}
result;
}
public void weave(List<Integer> first, List<Integer> second, List<Integer> prefix, List<List<Integer>> weaved) {
if (first.isEmpty() || second.isEmpty()) {
List<Integer> result = prefix.clone();
result.addAll(first);
result.addAll(second);
weaved.add(result);
return;
}
if (second.isEmpty()) {
weaved.add(prefix.addAll(first).clone());
prefix.removeAll(first);
return;
}
Integer firstTmp = first.removeFist();
prefix.addLast(firstTmp);
weave(first, second, prefix, weaved);
prefix.removeLast();
first.addFirst(firstTmp);
Integer secondTmp = second.removeFirst();
prefix.addLast(secondTmp);
weave(first, second, prefix, weaved);
prefix.removeLast();
second.addFirst(secondTmp);
}
|
评论