95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For 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

解法类似 241题：http://www.jianshu.com/p/91b3c4352b43

Solution1：Divide and Conquer

以每个num=0...n都尝试作为起点，以num分成左右两部分part1 for [0..num - 1], part2 for [num + 1, n] (Divide)，recursiely计算part1和part2的建树结果，再将这两个组合结果Conquer构成从当前num分的结果。
Time Complexity: ？ Space Complexity: ？

Solution2：Divide and Conquer + Hashmap

Solution1中含有重复计算，2在Solution1的基础上将已求过的[start, end]的结果 Map<String, List<TreeNode>> cached_tree保存下来，缓存避免重复计算。
Time Complexity: ？ Space Complexity: ？

Solution3：DP写法

ret[n] 保存到n的结果(所有的unique BST)
根据96. Unique Binary Search Trees: http://www.jianshu.com/p/a49119ef97c3
的DP递推表达式

G(n): the number of unique BST for a sequence of length n.
F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.

G(0)=1, G(1)=1. 
G(n) = F(1, n) + F(2, n) + ... + F(n, n). 
F(i, n) = G(i-1) * G(n-i)   1 <= i <= n 
So, 
=>    G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

思路相同，这不过这里是把G当作实际的BSTs，G(0) 和 G(n-1) 做组合，G(1) * G(n-2)做组合，...都加到结果中。做组合时树：node.value = j, 左侧的是left children，右侧的是right children(需shift)，
Example G(4) 如下图所示：

屏幕快照 2017-09-04 下午11.43.50.png

n = sum of the total number of unique binary trees
Time Complexity: n？ Space Complexity: n？

Solution1 Code：

class Solution1 {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        return genTrees(1,n);
    }
        
    public List<TreeNode> genTrees (int start, int end) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(start > end) list.add(null);
        else if(start == end) list.add(new TreeNode(start));
        else {
            // start < end
            List<TreeNode> left,right;
            for(int i = start; i <= end; i++) {
                // Divide
                left = genTrees(start, i - 1);
                right = genTrees(i + 1, end);

                // Conquer
                for(TreeNode lnode: left) {
                    for(TreeNode rnode: right) {
                        TreeNode root = new TreeNode(i);
                        root.left = lnode;
                        root.right = rnode;
                        list.add(root);
                    }
                }
            }
        }
        return list;
    }
}

Solution2 Code：

class Solution2 {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        return genTrees(1,n);
    }
    
    private Map<String, List<TreeNode>> cached_tree = new HashMap<>();
        
    public List<TreeNode> genTrees (int start, int end) {
        // find if there has been cached already
        String key = "" + start + "." + end;
        if(cached_tree.containsKey(key)) return cached_tree.get(key);
        
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(start > end) list.add(null);
        else if(start == end) list.add(new TreeNode(start));
        else {
            // start < end
            List<TreeNode> left,right;
            for(int i = start; i <= end; i++) {
                // Divide
                left = genTrees(start, i - 1);
                right = genTrees(i + 1, end);

                // Conquer
                for(TreeNode lnode: left) {
                    for(TreeNode rnode: right) {
                        TreeNode root = new TreeNode(i);
                        root.left = lnode;
                        root.right = rnode;
                        list.add(root);
                    }
                }
            }
        }
        cached_tree.put(key, list);
        return list;
    }
}

Solution3 Code：

class Solution3 {
    // G(0)=1, G(1)=1. 
    // G(n) = F(1, n) + F(2, n) + ... + F(n, n). 
    // F(i, n) = G(i-1) * G(n-i)   1 <= i <= n 
    // =>
    // G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 
    
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        
        // dp init
        List<TreeNode>[] res = new List[n+1];
        res[0] = new ArrayList();
        res[0].add(null);
        res[1] = new ArrayList();
        res[1].add(new TreeNode(1));
        
        // dp
        for(int i = 2; i <= n; i++){
            res[i] = new ArrayList();
            for(int j = 1; j <= i; j++){
                for(TreeNode nodeL: res[j - 1]){
                    for(TreeNode nodeR: res[i - j]){
                        TreeNode node = new TreeNode(j);
                        node.left = nodeL;
                        node.right = clone(nodeR, j);
                        res[i].add(node);
                    }
                }
            }
        }
        return res[n];
    }
    
    private TreeNode clone(TreeNode n, int offset) {
        if (n == null) {
            return null;
        }
        TreeNode node = new TreeNode(n.val + offset);
        node.left = clone(n.left, offset);
        node.right = clone(n.right, offset);
        return node;
    }
}

95. Unique Binary Search Trees II