LeetCode_117_UniqueBinarySearchTrees

1. question: 不同的二叉搜索树（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-binary-search-trees

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

2. answers

这道题没想出来，参考了题解。主要有一下几个要点：

1. 求解整数n的所有二叉搜索树，那么[1,n]之间每一个数都可作为根节点出现。

2. 比如数字x，那么[1,x]只能作为左子树出现，[x,n]只能作为右子树。

3. 显然，x作为根节点形成的二叉搜索树的数量 = [1,x]形成的二叉搜索树数量 * [x,n]形成的二叉搜索树数量。

4. 那么n所有的二叉搜索树，就是[1,n]各个数形成的二叉搜索树数量之和，每个数都可由第3点求解。

5. [1,x]形成的二叉搜索树，其实就回归到本题了。

6. [x,n]形成的二叉搜索树，该怎么求解呢？因为题目求解的是数量，显然对于数值没有太大的要求。对于[x,n]形成的二叉搜索树，其实和[1, n-x]形成二叉搜索树是一样的，因为元素的相对大小都是完全匹配的。

   比如[1,2,3,4]和[5,6,7,8]四个数，其实形成的二叉搜索树是一样的。

7. 此时，n形成的二叉搜索树，可由[1,x]和[1,n-x]求的。而x则是[1,n]之间的任意数。

8. 由此可得递推公式：dp[n] = (dp[0] * dp[n-1]) + (dp[1] * dp[n-2]) + (dp[2] * dp[n-3]) + … + (dp[n-1] * dp[0])

注意，因为根节点占用了一个数，所以左右子树节点之和为n-1。

设dp[x]表示[1,x]所形成的所有二叉搜索树总数。

另外，左子树为空，显然本数的二叉搜索树总数取决于右子树，即dp[0]为1。代码如下所示：

public class Solution_0117 {

    public int numTrees(int n) {

        if(n <= 2) return n;

        // 初始化数组
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {

            // 计算dp[i]，即[1,i]之间每个数都作为一遍根节点
            // 注意，因为根节点的存在，所以左右子树的节点数之和要减1，即i-1
            // 此时，j表示左子树的节点数量，即[0, i-1]
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - 1 -j];
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0117 s = new Solution_0117();

        System.out.println(s.numTrees(3));
    }
}

其实对于dp[2]，也可以不初始化。代码如下所示：

public int numTrees(int n) {

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

    for (int i = 2; i <= n; i++) {

        for (int j = 0; j < i; j++) {

            result[i] += result[j] * result[i-1 - j];
        }
    }

    return result[n];
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。