Given n, generate all structurally unique BST's (binary search trees) that store values 1...n
Solution: 根据[start, end]构造,取其中的i作为root,则[start, i - 1]为left, [i + 1, end]为right,产生的left和right的list两两组合
public List<TreeNode> generateTrees(int n) {
return generate(1, n);
}
private List<TreeNode> generate(int start, int end){
List<TreeNode> result = new ArrayList<TreeNode>();
if(start > end){
result.add(null); //不能少
return result;
}
if(start == end){
result.add(new TreeNode(start));
return result;
}
for(int i = start; i <= end; i++){
List<TreeNode> left = generate(start, i - 1);
List<TreeNode> right = generate(i + 1, end);
for(TreeNode leftroot : left){
for(TreeNode rightroot : right){
TreeNode root = new TreeNode(i);
root.left = leftroot;
root.right = rightroot;
result.add(root);
}
}
}
return result;
}
.