96. Unique Binary Search Trees I

Unique Binary Search Trees I：

https://leetcode.com/problems/unique-binary-search-trees/description/
解题思路：

1. 对于n：把从1到n分别作为根节点，然后左子树*右子树，最后对其全部相加即可

class Solution {
public int numTrees(int n) {

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

}

Unique Binary Search Trees II：

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

解题思路：

1. 思想如上题，但是在每一步需要create TreeeNode

class Solution {
public List<TreeNode> generateTrees(int n) {

    List<TreeNode>[] dp = new List[n + 1];
    dp[0] = new ArrayList<TreeNode>();
    if(n == 0) return dp[0];
    dp[0].add(null);
    for(int i = 1; i <= n; i++){
        dp[i] = new ArrayList<TreeNode>();
        for(int j = 1; j <= i; j++){
            for(TreeNode nodeL : dp[j-1]){
                for(TreeNode nodeR : dp[i - j]){
                    TreeNode node = new TreeNode(j);
                    node.left = nodeL;
                    node.right = clone(nodeR, j);
                    dp[i].add(node);
                }
            }
        }
    }
    return dp[n];
}

public TreeNode clone(TreeNode node, int offset){
    if(node == null){
        return null;
    }
    TreeNode newNode = new TreeNode(node.val + offset);
    newNode.left = clone(node.left, offset);
    newNode.right = clone(node.right, offset);
    return newNode;
}

}