首页 > 其他 > 详细

【LeetCode】不同二叉搜索树

时间:2019-10-15 18:26:40      阅读:98      评论:0      收藏:0      [点我收藏+]

【问题】

卡特兰(Catalan)数来源于卡特兰解决凸n+2边形的剖分时得到的数列Cn,在数学竞赛、信息学竞赛、组合数学、计算机编程等方面都会有其不同侧面的介绍.卡特兰问题的解决过程应用了大量的映射方法,堪称计数的映射方法的典范.

假设h(0) = 1, h(1) = 1, 则卡特兰数满足以下递推式:
h(n) = h(n-1) * (4 * n-2)/(n+1)----十分重要的递推式

那么,给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

【思路】

由于题目是不同的二叉搜索树,那么就与每个节点的值无关了,只考虑构成二叉树的结构问题!

思路一:使用动态规划算法,假设有i个节点构成二叉树,以根节点分割,左子树有j个节点,则:
dp[i] = dp[j] * dp[i-j-1]
其中dp[i]表示节点总数为i时可以有多少种方案,就等于左子树的方案数*右子树的方案数

思路一:动态规划
class Solution {
public:
    int numTrees(int n) {
        vector<long> dp(n+1);
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i-j-1];
            }
        }
        return dp[n];
    }
};

思路二:使用卡特兰数递推式,由于二叉树的构成问题属于卡特兰数的一种应用!我们可以直接使用递推式得到最终的结果!

思路二:卡特兰数
class Solution {
public:
    int numTrees(int n) {
        long h = 1;
        for(long i = 1; i <= n; ++i){
            h = h * (4*i-2) / (i+1);
        }
        return h;
    }
};

【LeetCode】不同二叉搜索树

原文:https://www.cnblogs.com/zhudingtop/p/11678964.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!