95 Unique Binary Search Trees II
https://leetcode.com/problems/unique-binary-search-trees-ii/#/description
Given an integern, generate all structurally uniqueBST's(binary search trees) that store values 1...n.
For example,
Givenn= 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析及代码
public List<TreeNode> generateTrees(int n) {
if(n < 1) {
return new ArrayList<TreeNode>();
}
return generate(1, n);
}
private List<TreeNode> generate(int start, int end) {
List<TreeNode> list = new ArrayList<>();
if(start > end) {
list.add(null);
return list;
}
if(start == end) {
list.add(new TreeNode(start));
return list;
}
for(int i = start; i <= end; i++) {
List<TreeNode> left = generate(start, i - 1);
List<TreeNode> right = generate(i + 1, end);
for(TreeNode leftSubtree: left) {
for(TreeNode rightSubtree: right) {
TreeNode root = new TreeNode(i);
root.left = leftSubtree;
root.right = rightSubtree;
list.add(root);
}
}
}
return list;
}
只能这样暴力解
要注意的是,在generate()函数里面, if(start > end), list还是要add(null);