96. Unique Binary Search Trees - jiejackyzhang/leetcode-note GitHub Wiki

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         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Tree类题目。

解题思路为Dynamic Programming。

1,...,n每一个都可以作为root。 令i为root，则[1,i-1]为左子树，[i+1,n]为右子树。 这个过程可以通过recursion完成。

这里的问题是要求出一共有多少unique BST。 令P[i]表示长度[1,i]的BST个数，F(j,i)表示以j为root，范围为[1,i]的BST个数。 则：

P[i] = F(1,i) + F(2,i) + ... + F(i,i)

若以j为root，则左子树的排法共有P[j-1]种，右子树的排法共有P[i-j]中，因此：

F(j,i) = P[j-1]*P[i-j]

Basic cases为：

P[0] = 1, 即树为空

最后，P[n]即为所求。

public class Solution {
    public int numTrees(int n) {
        int[] p = new int[n+1];
        p[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                p[i] += p[j-1] * p[i-j];
            }
        }
        return p[n];
    }
}