☆打卡算法☆LeetCode 96、不同的二叉搜索树 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个整数n，求由n个节点组成的节点值从1到n的互不相同的搜索二叉树。”

题目链接：

来源：力扣（LeetCode）

链接：96. 不同的二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
输入： n = 3
输出： 5

示例 2：
输入： n = 1
输出： 1

二、解题

1、思路分析

这道题95题【不同的二叉搜索树 Ⅱ】很相似，不同的点在于这道题要找出互不相同的二叉搜索树。

上一题我们使用了递归的方法，找出所有能构建的二叉搜索树，然后再在其中找出合法的二叉搜索树。

而在遍历每个数字的过程中，可以将该数字作为树根，然后将1…i-1作为左子树，i+1…n作为右子树，然后按照同样的方式递归构建左子树和右子树。

也就是把一个问题分成两个小问题，因此可以使用动态规划来解这道题：

• 假设n个节点存在二叉排序树的个数为G_n，然后每个数字作为根也就是f(1)-f(n)，则
• G(n)=f(1)+f(2)+f(3)+f(4)+…+f(n)
• 当i为根节点时，其左子树节点数为1…i-1，右子树的节点数为i+1…n，则
• f(i)=G(i-1) * G(n-i)
• 综合两个公式可以得到卡特兰数公式：
• G(n) = G(0) * G(n-1) + G(1) * (n-2) + … + G(n-1) * G(0)

2、代码实现

代码参考：

class Solution {
    public int numTrees(int n) {
        // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n表示二叉搜索树的节点个数。

空间复杂度： O(1)

只需要常量级的空间存放变量。

三、总结

这里分享一个面向测试用例的编程代码，非常的秀：

class Solution {
public:
    int numTrees(int n) {
        switch(n){
            case 1: return 1;
            case 2: return 2;
            case 3: return 5;
            case 4: return 14;
            case 5: return 42;
            case 6: return 132;
            case 7: return 429;
            case 8: return 1430;
            case 9: return 4862;
            case 10: return 16796;
            case 11: return 58786;
            case 12: return 208012;
            case 13: return 742900;
            case 14: return 2674440;
            case 15: return 9694845;
            case 16: return 35357670;
            case 17: return 129644790;
            case 18: return 477638700;
            case 19: return 1767263190;
            default: return 0;
        }
    }
};

因为答案的值是固定的，所以这么写。。。好像也能通过。。。