不同的二叉搜索树

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

示例

输入：n = 3

输出：5

思路

一开始看到这道题没什么思路，先试着从1开始画出所有二叉搜索树来看看有没有规律。

观察n=3时画出的二叉搜索树，可以发现：

• 根节点为1时，右子树有两个节点，且形状跟n=2时的二叉搜索树形状数量相同
• 根节点为2时，左右子树各有一个节点，跟n=1时相同
• 根节点为3时，与根节点为1时同理

根节点固定时，二叉搜索树数量就等于n=左子树节点数量时二叉搜索树数量乘以n=右子树节点数量时二叉搜索树数量。

定义数组dp，dp[i]代表1到i组成的二叉搜索树数量。当n=i时，以j为根节点的二叉搜索树数量为dp[j-1]*dp[i-j]，j-1为左子树节点数量，i-j为右子树节点数量。dp[0]为多少呢？为了不让两边相乘为0，dp[0]当然为1，并且没有节点也可以理解为一种二叉搜索树。

所以只需要遍历1到i，让1到i都成为一次根节点，算出每次的二叉搜索树数量并且加起来：dp[i]+=dp[j-1]*dp[i-j]就得到了dp[i]。

要算出dp[n]，就要从前往后遍历依次算出dp[i]，因为后面的计算依赖于前边的结果。

代码实现

class Solution {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        for(int i=1;i<n+1;i++) {
            for(int j=1;j<i+1;j++) {
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}