leetcode solution 96 Unique Binary Search Trees
z
 2018-03-19 22:02:54  

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

For example,
Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            for(int j=1; j<=i; j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}
  • 对于n = 5
  • 1 2 3 4 5
  • dp[0] = 1
  • dp[1] = 1
  • dp[2] =当1为根节点和当2为更节点之和
  • dp[4]
    • 1为根节点 + 2为根节点 + 3为根结点 + 3为根节点
    • 当j为根节点时， 可能的组合为 左子树的可能组合*右子树的可能组合
    • 假设跟个节点为2， 左子树 1 右子树 3 4 ，而3 4 等价于 1 2