M-LC96-不同的二叉搜索树

LeetCode
Word count: 620   |   Reading time ≈ 2 min

题目描述

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

示例 1：

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 19

解题思路

前段时间做这题没做出来，一直搁置着，今天再次分析了一下，发现也没那么难。
首先需要明确二叉搜索树的特性：左子树的元素都比根小，右子树的元素都比根大。因此，我们很容易想到将 n 个节点 [1,2,3,…,n] 分为三部分：左子树节点、根节点、右子树节点，且三部分的顺序一定是从左到右。

题目要求返回满足题意的二叉搜索树的种数，因此在根结点固定的条件下，我们只需关注左右子树的节点数量。下表列出了 n 从 1 到 5 的分法：

n 划分方案
根结点 => (左子树节点数量, 右子树节点数量)
1 1 => (0,0)
2 1 => (0,1)
2 => (1,0)
3 1 => (0,2)
2 => (1,1)
3 => (2,0)
4 1 => (0,3)
2 => (1,2)
3 => (2,1)
4 => (3,0)
5 1 => (0,4)
2 => (1,3)
3 => (2,2)
4 => (3,1)
5 => (4,0)

各个方案之间是平行的关系，因此将各个方案对应的二叉搜索树的数量加和即可。单独看左子树节点或右子树节点，仍然是求二叉搜索树数量的问题。

通过上表，可以较容易的推导出该问题的递推关系：若f(n)f(n)代表nn个节点对应的二叉搜索树的数量，则：

f(n)=∑i=0n−1f(i)×f(n−1−i)f(n)=\sum_{i=0}^{n-1}f(i)\times f(n-1-i)

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    //记录中间结果，防止超时
    map<int, int> memo;

    int numTrees(int n) {
        if (n == 0)
            return 1;
        if (memo[n])
            return memo[n];
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += (numTrees(i) * numTrees(n - i - 1));
        memo[n] = ans;
        return ans;
    }
};

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    //动态规划
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++)
                dp[i] += (dp[j] * dp[i - j - 1]);
        }
        return dp[n];
    }
};