LeetCode.96.不同的二叉搜索树（中等）

题目

LeetCode.96.不同的二叉搜索树（中等）

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

提示： 1 <= n <= 19

题解

树的问题第一反应会想到递归，进而想到能不能划分子问题。

从基本情况开始梳理。
构造一棵树，要选一个根节点。
如果以某个数字为根节点，左子树有a种，右子树有b种，那么这棵树就有a * b种可能。

左子树和右子树的构建，也要选择根节点，选择逻辑一样，可以递归进行，但是能选的根节点数量少了一个。

递推下去可以发现，如果剩余可选节点数越少，种数就越少。

设sum[i]为节点总数为i的二叉搜索树的种数。
除去根节点，假设左子树有j个节点，右子树就有i - 1 - j个节点，其中j的取值范围是0 <= j <= i - 1，得把所有的j可能情况都取一遍值，最后累加结果，就得到sum[i]。

状态转移方程
sum[i]= ∑ sum[j] * sum[i - 1 - j]，0 <= j <= i - 1

边界处理
总共只有0个节点，是空树，也算一种树，sum[0] = 1。想象一下如果左子树为空，右子树有n种，那么当前树也应该有n种。
总共只有1个节点，只有一种情况，sum[1] = 1。

class Solution {
    fun numTrees(n: Int): Int {
        val sum = IntArray(n + 1) { 0 }
        sum[0] = 1
        sum[1] = 1
        for (i in 2..n) {
            for (j in 0 until i) {
                sum[i] += sum[j] * sum[i - 1 - j]
            }
        }
        return sum[n]
    }
}