Unique Binary Search Trees

文章目录

1. 1. Unique Binary Search Trees
   1. 1.1. 题目
   2. 1.2. 思路
   3. 1.3. 解题

Unique Binary Search Trees

题目

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，当i作为root时，小于i的点都只能放在其左子树中，大于i的点只能放在右子树中，此时只需求出左、右子树各有多少种，二者相乘即为以i作为root时BST的总数。

解题

c++版

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=0; j<i; j++)  
                    num[i]+=num[j]*num[i-j-1];  
            }  
        }  
        return num[n]; 
    }
};

python版

class Solution:
    # @param {integer} n
    # @return {integer}
    def numTrees(self, n):
        num=[1]
        for i in range(1,n+1):
            num.append(0)
            if(i<3):
                num[i]=i
            else:
                for j in range(0,i):
                    num[i]+=num[j]*num[i-j-1]
        return num[n]