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-n中选择i作为根,其可能出现的情况为[1,i-1]中BST种类 和 [i+1,n]中BST种类的 乘积, 因此n个节点的总可能性就是把1到n逐步作为根节点的情况总数,而每一个情况又可以按照同样的方式继续计算,因此,我们可以将问题逐步缩小。tip:可以用DP讲计算过的结果存储起来。


public class Solution {
    public int numTrees(int n) {
        
        return numTree(1,n);  
    }
    
    int numTree(int start, int end)  
    {  
        if (start >= end)  
            return 1;  
  
        int totalNum = 0;  
        for (int i=start; i<=end; ++i)  
            totalNum += numTree(start,i-1)*numTree(i+1,end);  
        return totalNum;  
    }  
}

Advertisements
This entry was posted in 算法题, Tree. Bookmark the permalink.

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