Leetcode 题目解析：96. 不同的二叉搜索树

系列文章：

算法题目解析：从一道题目看动态规划

Leetcode 题目解析：274. H 指数

Leetcode 题目解析：279. 完全平方数

Leetcode 题目解析：287. 寻找重复数

Leetcode 题目解析：211. 添加与搜索单词 - 数据结构设计

Leetcode 题目解析：70. 爬楼梯

一 动态规划题目

本篇选择另一道题目来继续练习动态规划算法。leetcode的第96题：96. 不同的二叉搜索树。

二 不同的二叉搜索树

2.1 题目描述

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

2.2 示例

输入：n = 3
输出：5

三 解析

3.1 题目解析

给定一个整数n，实际上就是固定了一个{1,2,3,...,n}的数组，希望用这些元素组成一个二叉搜索树，即要满足构成的树，根的左节点值总是小于根节点值，且右子树中的节点都大于根节点值。

为了构建出一棵二叉搜索树，我们可以从1到n遍历每个数字，在每一轮，把当前遍历的数字作为树的根节点值，1，⋯，i−1作为左子树，将i+1，⋯，n 作为右子树。如此我们也可以按照同样的方式递归构建左子树和右子树。因为这样构建的根节点值是不同的，所以得到的二叉树也是唯一的，不会与其他轮构建的二叉树重复。

通过这样的分析，每一轮的问题都可以分解成规模较小的两个子问题，且子问题的解可以复用，从而符合动态规划的条件。

3.2 示例解析

示例给出的n=3，也就是用{1,2,3}生成二叉搜索树，看能够生成几个不同的二叉搜索树。

从示例给出的几个二叉搜索树的图，已经可以初步分析出一些东西。首先，分别用1，2，3 作为根节点。

• 1作为根节点，因为没有比1小的数，所以2，3只能在1的右子树出现；{2,3}数组，分别用2，3作为子树的根节点，有两种可能；所以1作为根节点，共2种可能的树结构；
• 2作为根节点，1比2小，所以只能在左子树；3比2大，只能在右子树，所以共1种可能；
• 3作为根节点，没有比3大的数，所以1，2只能在3的左子树出现；{1，2}数组，分别用1，2作为左子树的根节点，有两种可能；所以3作为根节点，共2种可能的二叉搜索树

上述3种情况合计，共2+1+2=5种可能，所以输出=5。

3.3 解法思路

基于3.2对示例的分析，我们可以定义两个函数：（1） G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数；（2）F(i,n): 以 i 为根，数组长度为 n 的不同二叉搜索树个数(其中，1≤i≤n)；那么，G(n)就是题目的解。

不同的二叉搜索树的总数，是对遍历所有i的 F(i, n) 之和。也就是：

这个就是这道题目的状态转移方程；除此之外，我们还要确定边界条件（再敲黑板画重点：动态规划的两大要素）。当n=0时，是空数组，只能构建成空树，所以G(0)=1；当n=1时，只有一个元素，构建的树就只能有一个根节点，G(1)=1；由此向下，可以得到：

3.4 代码实现

public int numTrees(int n) {
    int[] G = new int[n + 1];
    G[0] = 1;
    G[1] = 1;

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
}

四 小结

与上一篇中的70. 爬楼梯问题相比，显然这次的问题难了一些。爬楼梯问题是很直白的动态规划问题。而96. 不同的二叉搜索树这道题涉及了二叉搜索树，并且需要先根据输入数组，与二叉搜索树的特性，分析并确认能得到状态转移方程。看似只是融入了一个新的概念，但复杂度要高了很多，所以这是一道中等难度的题目。

在开始做动态规划类的题目时，先硬记几类动态规划题目倒也未尝不可。只不过需要明白，要记的是分析方法和思考方式，而不是代码。在有了这些基础之后，才能够做到万变不离其宗，“大道至简”。