96、不同的二叉搜索树

一、题目描述

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

示例 1：

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

输入：n = 1
输出：1

提示：
1 <= n <= 19

二、C++代码

解法一：

这种题目，我一般是计算出前面多个例子，根据计算出来的多个例子，进行归纳总结，利用数学归纳法，找规律，推算出第n个的结果，然后利用类似如下方法，根据第0个，第1个，第2个……，以此计算出第n个。

n=1,搜索二叉树种数：1 ,只有一个节点，所以为1

n=2,搜索二叉树种数：2 ,只有二个节点，要么1为根节点，要么2为根节点，所以结果为2

n=3,搜索二叉树种数：5 ,有三个节点
(1)、1为根节点，另外两个节点，均大于1，根据二叉搜索树的性质，大于根节点的数字，即另外两个节点2和3只能作为右子树，再作为一个整体，构成二叉搜索树，此时另外两个节点构成结果等同于n=2时的结果，为2
(2)、2为根节点，根据二叉搜索树性质，1只能作为左子树，3只能作为右子树，只有一种情况，所以结果为1
(3)、3为根节点，根据二叉搜索树性质，1和2只能作为左子树,1和2作为一个整体再构成二叉搜索树，此时与(1)一样，结果等于n=2时的结果为2
所以n=3时，搜索二叉树种数为2+1+2=5

n=4,搜索二叉树种数：14
(1)、1为根节点，另外三个节点，均大于1，另外节点只能作为右子树，其他节点再作为一个整体，构成二叉搜索树，此时另外三个节点构成结果等同于n=3时的结果，为5
(2)、2为根节点，根据二叉搜索树性质，1只能作为左子树，3,4只能作为右子树，此时进行排列组合，即为n=1和n=2的结果相乘，为2
(3)、3为根节点，结果等于(2)时的结果为2
(3)、4为根节点，结果等于(1)时的结果为5

n=5,搜索二叉树种数：42
……
所以我总结规律为当输入数字为100,结果应该为n=0 * n=99 + n=1 * n=98 + …… + n=99 * n=0, n=0时为1

class Solution {
public:
    
    int numTrees(int n) {
        int i = 0;
        int res = 0;
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (n == 3) {
            return 5;
        }

        for (i = 0; i < n; ++i) {
            res += (numTrees(i) * numTrees(n- 1 - i));
        }
        
        return res;
    }
};

解法二：
解法一比较耗时，所以在解法一基础上进行优化，可以把中间的结果都保存到数组nums中，后续就不需要每次都遍历才拿到结果了。

class Solution {
public:
    int numTrees(int n) {
        vector<int> nums(20, 0);
        nums[0] = 1;
        traverse(n, nums);
        return nums[n];
    }

    int traverse(int n, vector<int> &nums)
    {
        int res = 0;
        int i = 0;
        if (nums[n] != 0) {
            return nums[n];
        }

        for (i = 0; i < n; ++i) {
            nums[n] += (traverse(i, nums) * traverse(n- 1 - i, nums));
        }
        return nums[n];
    }
};

解法3：
动态规划，后续再写具体思路吧：

class Solution {
public:
    int numTrees(int n) {
        // 二叉搜索数的特征，左子树小于根，右子树大于根
        vector<int> dp(n+1, 0);
        dp[0]=1;  // dp[0]初始化为1
        for(int i=1; i<=n; i++)  // 从1...n的二叉搜索数数目
            for(int j=1; j<=i; j++)  // 逐步选用1...n作为根节点
                dp[i]+=dp[j-1]*dp[i-j];  // 左侧j-1个数，右侧i-j个数
        return dp[n]; 
    }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。