LeetCode - Unique Binary Search Trees II
Problem description
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Analysis
The first thought is to use the inorder traversal to get a result. And this can only get part result of the solution.
And the solution from LeetCode is using divide and conquer.
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
class Solution {
public LinkedList<TreeNode> generate_trees(int start, int end) {
LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
if (start > end) {
all_trees.add(null);
return all_trees;
}
// pick up a root
for (int i = start; i <= end; i++) {
// all possible left subtrees if i is choosen to be a root
LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);
// all possible right subtrees if i is choosen to be a root
LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);
// connect left and right trees to the root i
for (TreeNode l : left_trees) {
for (TreeNode r : right_trees) {
TreeNode current_tree = new TreeNode(i);
current_tree.left = l;
current_tree.right = r;
all_trees.add(current_tree);
}
}
}
return all_trees;
}
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<TreeNode>();
}
return generate_trees(1, n);
}
}
What to improve
- think if this method can solve the question.