不同的二叉搜索树

力扣 96. 不同的二叉搜索树

题目说明

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

提示：

1 <= n <= 19

示例

示例 1:

1 2	输入：n = 3 输出：5

示例 2:

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

笔者理解

此题是一道动态规划算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现我们只需要依次讨论 2 - n 个节点的可能即可，每个可能只需要讨论左子树的可能和右子树可能的乘积即可，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 动态规划
     * 左右划分
     */
    public int numTrees(int n) {
        if (n < 2) {
            return 1;
        }

        int[] sums = new int[n + 1];
        sums[0] = 1;
        sums[1] = 1;

        for (int i = 2; i < n + 1; i++) {
            sums[i] = 0;
            for (int j = 0; j < i; j++) {
                // 排列组合
                // sums[j] 左子树的可能
                // sums[i - j - 1] 右子树的可能
                sums[i] = sums[i] + sums[j] * sums[i - j - 1];
            }
        }
        
        return sums[n];
    }
}