[LeetCode] 96. Unique Binary Search Trees

正午 2020-01-09 PM 16℃ 0条

题目描述

给定一个正整数 n , 1 到 n 组成的数能有多少种二叉搜索数
二叉搜索树满足左孩子小于跟节点,有孩子大于根结点的规律。

解法一

当根节点确定的情况下,左子树和又子树的节点数求和为 n-1 个 而且共有 n 种分配方法,当分配方案确定之后,原问题可以分解左子树的个数 * 右子树的个数。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        if (n==1 || n==0){
            return 1;
        }
        //  令 dp[0] = 1
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<= n; i++){
            for(int j=0; j<i; j++){
                dp[i] += dp[i-j-1] * dp[j];
            }
        }
        return dp[n];
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论