Unique Binary Search Trees, Leetcode 解题笔记

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

这道题同样让人没有思路,其实就是找规律:
递归 一共n个,root是1个(可能是1:n中的一个),左边分到比root小的i-1个,右边分到比root大的n-i个,左边的组合数*右边的组合数

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s