leetcode刷题笔记，96.不同的二叉搜索树。

96.不同的二叉搜索树

题目

https://leetcode.cn/problems/unique-binary-search-trees/

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

image.png

思路

这道题是道动态规划的题目，动态规划的最重要的就是找到迭代的方程。

可以先举例几个不同的二叉搜索树情况，再找找有没有啥规律可循。首先是最简单的单个节点和两个节点的树，单个节点的二叉树只有1种情况，两个节点的二叉树有2种情况。

image.png

如果是三个节点的二叉搜索树呢？以leetcode给出的示例图

image.png

从图中可以总结出三种不同的情况，假设f(x)为有x元素的二叉搜索树的种类个数。

  • 当1为根节点的时候，左子树为空，右子树2个元素，那么当前树的形态数量就是 f(0) * f(2)，即只由右边的两个元素的树的形态数量决定；
  • 当2为根节点的时候，左右子树都有1个元素，此时树的形态数量是 f(1) * f(1)，即由两个元素只有1的树的形态数量组合决定；
  • 当3为根节点的时候，右子树为空，左子树2个元素，这和1为根节点的情况类似，即当前树只由左边两个元素的树的形态数量决定，f(2) * f(0)；

由此可得x为3的时候二叉搜索树的种类的计算公式

$$
f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
$$

这里就还需要确定一下f(0)应该是什么值了，因为空树也可以视作树的一种情况，再加上在当前的递推公式种涉及到了对f(0)的计算，所以应该将其初始化为1。否则计算的时候相关的值都为0了。

上面的这个公式结论，还可以推广到i个节点的树的情况：

$$
f(i) = f(0) * f(i-1) + f(1) * f(i-2) + … + f(i-1) * f(0)
$$

我们需要计算有n个节点的二叉搜索树种类，可以用这个递推公式一直从1计算到n，即可得到最终的结果。其本质就是将一个大的二叉搜索树不断拆分成小的树。

关于拆分这一点，可以参考一篇写的还不错的题解，详细介绍了整个拆分的思路。

我们可以认为我们需要遍历的是一个1到n的数组，那么从这个数组中，不管从哪一个位置“提起”这棵树，最终得到的都是一个符合二叉搜索树规定的树（可以参考从有序数组构造二叉搜索树的OJ题）。这样我们就可以使用二分的思想不断将树拆分，直到拆分成只有1个元素的树的情况。

那么代码中应该怎么处理呢？这里需要多层循环，我们需要将计算公式改成循环的累加（总不可能一直写个很长的公式吧）

首先外层循环是从1递推到n，内层循环是进行每一次有i个元素的二叉搜索树的节点数量计算。这样就实现了递推的计算。

1
2
3
4
5
6
7
// i代表当前树中有几个节点
for (int i = 1; i <= n; i++) {
    // j是单个循环中的处理，我们需要从0 * i-1 一直走到 i-1 * 0
    for (int j = 1; j <= i; j++) {
        v[i] += v[j - 1] * v[i - j];
    }
}

代码

完整代码如下，注意vector中的所有元素需要初始化为0，否则无法正常进行累加。根据上述思路将v[0]=1初始化，然后用循环一直计算到n，最后v[n]就是我们需要的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int numTrees(int n) {
        vector<int> v(n + 1, 0);
        v[0] = 1; // 没有节点的数也算一颗树
        // i代表当前树中有几个节点
        for (int i = 1; i <= n; i++) {
            // j是单个循环中的处理，我们需要从0 * i-1 一直走到 i-1 * 0
            for (int j = 1; j <= i; j++) {
                v[i] += v[j - 1] * v[i - j];
            }
        }
        return v[n];
    }
};
// 下面这个题解比较好理解一些。首先要知道这个题目的答案是可以被缩小范围的
// https://leetcode.cn/problems/unique-binary-search-trees/solutions/331743/er-cha-sou-suo-shu-fu-xi-li-zi-jie-shi-si-lu-by-xi/

// 需要得出某个值为根节点的时候，这颗树的形态个数是(左边节点数量时的形态个数)*(右边节点数量时的形态个数)
// 以[1,2,3]为例
// 当1为根节点的时候，左子树为空，右子树2个元素，那么当前树的形态数量就是 f(0) * f(2)，即只由右边的两个元素的树的形态数量决定
// 当2为根节点的时候，左右子树都有1个元素，此时树的形态数量是 f(1) * f(1)，即由两个元素只有1的树的形态数量组合决定
// 当3为根节点的时候，右子树为空，左子树2个元素，这和1为根节点的情况类似，即当前树只由左边两个元素的树的形态数量决定，f(2) * f(0)
// 这下就可以得到公式 f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
// 进一步得到i的公式 f(i) = f(0) * f(i-1) + f(1) * f(i-2) + ... + f(i-1) * f(0)
// 我们要做的就是把这个公式转换成一个循环中的累加，即上面代码中的for循环。
// 注意vector中的值应该都初始化为0，不然累加的时候会出问题。

image.png