leetcode题解---96.不同的二叉搜索树_不同的二叉搜索树 leetcode

96.不同的二叉搜索树（dp）

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

思路：动态规划最重要的就是找状态转移方程，这也是最难的，dp之所以比回溯快，是因为dp问题大多存在很多重复的子问题，感觉dp问题的重点是先将大问题划分为一个个重叠小问题，然后由底向上一步步解决，中途利用辅助数组记录每个子问题的值，这样使得每个子问题只需要计算一次就行，大大节省了时间。感觉将大问题拆解为一个个小问题之后，可以先从最小的问题慢慢向上推，然后列出状态转移方程。这样基本上就问题不大了。

这道题求n个节点可以组成多少种二叉搜索树。先从1个节点开始，一个节点肯定只能组成1种；然后n=2,不难发现，答案是2，当n=3时，我们也可以在纸上画出来，答案是5，这样好像没有发现什么。我们换种想法：

当n=3时，我们可以分别以1，2，3分别为根节点构造二叉搜索树。

• 以1根节点时，左子树没有节点，右子树有两个节点。而两个节点又可以构成两种不同的二叉搜索树，所以以1为根节点时，可以构造1*2种不同的二叉搜索树。

• 以2为根节点时，左子树又一个节点，右子树有一个节点，我们可以得出以2为节点时，可以构造1*1种不同的二叉搜索树

• 以3根节点时，左子树有两个节点，右子树没有节点。而两个节点又可以构成两种不同的二叉搜索树，所以以3为根节点时，可以构造2*1种不同的二叉搜索树。

• 所以n=3时，可以构造2 + 1 + 2 = 5中不同的二叉搜索树

以此类推，可以得到定义一个这样的函数searchNum(n)，用来求n个节点可以构造的不同二叉搜索树的种数。

函数代码如下：

private int searchNum(int n){
    int count = 0;

    for(int i = 1; i <= n; i++ ){
        count += searchNum(n - i) * searchNum(i - 1);
    }   
    return count;
}
1
2
3
4
5
6
7
8

然后发现求解的过程中，存在好多重复计算，于是使用备忘录memo优化，对于重叠子问题，只需要计算一次。最终代码如下：

class Solution {
    public int numTrees(int n) {
        int[] memo = new int[n + 1];
        memo[0] = 1;
        memo[1] = 1;
        return searchNum(n, memo);
    }

    private int searchNum(int n, int[] memo){
        if (memo[n] != 0) return memo[n];
        int count = 0;
       
        for(int i = 1; i <= n; i++ ){
            count += searchNum(n - i, memo) * searchNum(i - 1, memo);
        }   
        memo[n] = count;
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19