Unique Binary Search Trees

lc 96

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

这个题目要求返回数量。所以肯定感觉是dp来解决。 因为是bst，所以有一些性质，

The case for 3 elements example
Count[3] = Count[0]*Count[2]  (1 as root)
              + Count[1]*Count[1]  (2 as root)
              + Count[2]*Count[0]  (3 as root)

Therefore, we can get the equation:
Count[i] = ∑ Count[0...k] * [ k+1....i]     0<=k<i-1

public class Solution {

    public int numTrees(int n) {
        int[] count = new int[n + 1];
        count[0] = 1;
        count[1] = 1;

        for(int i=2;  i<= n; i++){
            for(int j=0; j<i; j++){
                count[i] += count[j] * count[i - j - 1];
            }
        }
        return count[n];
    }
}

lc 95

返回所有的可能性 dfs 就是取一个node，left一个，right一个，然后合并

ppublic class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0 ) return new ArrayList<TreeNode>();
        return generate(1, n);
    }
    private List<TreeNode> generate(int start, int end){
        List<TreeNode> rst = new ArrayList<TreeNode>();   

        if(start > end){
            rst.add(null);
            return rst;
        }

            for(int i=start; i<=end; i++){
                List<TreeNode> left = generate(start, i-1);
                List<TreeNode> right = generate(i+1, end);
                for(TreeNode l: left){
                    for(TreeNode r: right){
// should new a root here because it need to 
// be different for each tree
                        TreeNode root = new TreeNode(i);  
                        root.left = l;
                        root.right = r;
                        rst.add(root);
                    }
                }
            }
        return rst;
    }    


}