3月

LeetCode Unique Binary Search Trees

1.题目

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.

2.解决方案

 class Solution {  
    public:  
        int numTrees(int n) {  
            vector<int> num;  
            num.push_back(1);  
            for(int i=1; i<=n; i++){  
                num.push_back(0);  
                if(i<3)  
                    num[i]=i;  
                else{  
                    for(int j=1; j<=i; j++)  
                        num[i]+=num[j-1]*num[i-j];  
                }  
            }  
            return num[n];  
        }  
    };

思路：

我们先从0开始分析

0 当没有一个二分搜索树没有任何节点也是一种情况，即Tree[0] = 1

1 当一个二分搜索树只有一个节点也是一种情况，即Tree[1] = 1

2 当一个二分搜索树有2个节点时,肯定要有一个节点作为根节点，那样总的数量就是，Tree[2] = Tree[0] * Tree[1] + Tree[1] * [0]

3 当一个二分搜索树有3个节点时,肯定要有一个节点作为根节点，那样总的数量就是，Tree[3] = Tree[0] * Tree[2] + Tree[1] * [1] + Tree[2] * [0]

这里用了动态规划的思想，把之前已经算过的保存在数组中。

http://www.waitingfy.com/archives/1617

Post Views: 0