LeetCode 96 不同的二叉搜索树

96.不同的二叉搜索树

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

动态规划

此处要使用动态规划进行求解，首先需要完成对于问题的划分。要找到 1-n 个节点对应的不同形态得到二叉搜索树，那么最简单的划分方式就是：分别以 1-n 做根节点去建立树。

从 n=3 出发：

1. 前两棵树：就是将 1 作为根节点去建立树，右子树有两个节点，并且这两个节点的布局就和 n=2 时对应的二叉搜索树的布局相同。此处，将问题换一种方式去理解：给定一个整数 n ，求解的是 n 个数组成的二叉搜索树有多少种，但是不要求是 1-n 的数，仅仅是升序的 n 个数。左子树有0个节点，节点的布局就和 n=0 时对应的二叉搜索树的布局相同（与就是一棵空树）。那么此处就能够将 n=3 的情形与 n=2，0 情形建立联系。

2. 第三课树：将 2 作为根节点去建立树，左边一个节点，和 n=1 时对应的二叉搜索树的布局相同，右边一个节点，和 n=1 时对应的二叉搜索树的布局相同。那么此时就是将 n=3 与 n=1 情形建立联系。

3. 后两棵树：将 3 作为根节点去建立树，右子树有0个节点，节点的布局就和 n=0 时对应的二叉搜索树的布局相同（与就是一棵空树）。左子树有两个节点，并且这两个节点的布局就和 n=2 时对应的二叉搜索树的布局相同。那么此处就能够将 n=3 的情形与 n=2，0 情形建立联系。

最后 n=3 的计算方式为： dp[3]=dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2]

在此基础上使用动态规划进行求解：

1. 确定动态规划数组： dp[i] 表示 i 个整数组成的互不相同的二叉搜索树共有多少种。

2. 动态规划数组的递推公式：根据上述的推导过程可得： $dp[i]=\sum_{j=1}^{i}dp[i-j]*dp[j-1]$

3. 动态规划数组的初始化： dp[0]=1 对应于一棵空树的形态。

4. 数组的遍历顺序：计算 dp[i] 时需要使用到前值，从前向后计算。

5. 举例实现： n=2 那么 dp[1]=dp[0]*dp[0]=1 ， dp[2]=dp[1]*dp[0]+dp[0]*dp[1]=2 验证结果正确。

代码实现：

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

本题的重点在于：

1. 首先需要理解问题的划分：也就是对于一个包含 n 个节点的二叉搜索树，可以分为多少中情况，按照根节点的取值不同可以分为 n 种情况进行讨论。
2. 其次是对于每一种情况要如何构建树：对于根节点为 i 的情形，那么对应的二叉搜索树就应该是，左子树是一棵包含 i-1 个节点的二叉搜索树，右子树是一棵包含 n-i 个节点的二叉搜索树。
3. 对于 dp[i] 数组的理解转变：将其理解为包含 i 个节点的二叉搜索树有多少种形态，那么就和前面的问题划分实现了对应，将大问题划分了子问题。