Unique Binary Search Trees II 164
Question
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
Example
Given n = 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
Solution
用递归解,没用到DP?
依次遍历1-n,以当前的数为根节点。递归寻找当前数左边的所有数形成的BST的根节点,以及当前的数右边的所有数形成的BST的根节点,然后再遍历左右的根节点,将其依次插入当前数形成的根节点的左右两边(设左边有m个根节点,右边有n个根节点,则一共有m n种插入方法,因此以当前数为根节点会形成m n种BST),然后将当前数根节点插入result。
代码如下:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @paramn n: An integer
* @return: A list of root
*/
public List<TreeNode> generateTrees(int n) {
// write your code here
return generate(1, n);
}
private List<TreeNode> generate(int start, int end){
List<TreeNode> res = new ArrayList<TreeNode>();
if(start > end){
//将null加入res中,这样res永远不会为null,在返回的那层也就不用讨论res为null的情况
res.add(null);
return res;
}
if(start == end){
res.add(new TreeNode(start));
return res;
}
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;
res.add(root);
}
}
}
return res;
}
}