【LeetCode】动态规划—96. 不同的二叉搜索树（附完整Python/C++代码）

题目描述

前言

不同的二叉搜索树问题 是一个经典的动态规划问题。给定一个整数 n，我们需要构造出由 n 个节点组成的所有不同的 二叉搜索树（BST）。在这类问题中，我们不仅需要理解二叉搜索树的性质，还需要通过动态规划来计算不同形态的二叉搜索树的数量。

基本思路

1. 问题定义

给定一个整数 n，求由 n 个节点构成的所有不同的二叉搜索树的数量。每个二叉搜索树的节点包含从 1 到 n 的整数，每个整数只能使用一次。

2. 理解问题和递推关系

二叉搜索树的性质：

• 二叉搜索树（BST）的性质是，对于每个节点：
  • 左子树上所有节点的值都小于该节点的值。
  • 右子树上所有节点的值都大于该节点的值。

核心思路：

如果我们选择节点 i 作为根节点，那么：

1. 节点 1 到 i-1 会组成根节点 i 的左子树。
2. 节点 i+1 到 n 会组成根节点 i 的右子树。
3. 左子树和右子树的组合方式可以递归地进行计算，最终组合成完整的 BST。

状态定义：

设 dp[i] 表示 i 个节点能构成的不同二叉搜索树的数量。最终我们要求解的是 dp[n]。

状态转移方程：

对于每一个根节点 i，它的左子树有 i-1 个节点，右子树有 n-i 个节点。左子树和右子树的组合方式相乘，即：
$$dp[i]=\sum _{k=1}^{i}dp[k-1]\times dp[i-k]$$
其中，dp[k-1] 表示左子树的组合数，dp[i-k] 表示右子树的组合数。

边界条件：

• 当 n = 0 时，空树也是一种二叉搜索树，因此 dp[0] = 1。

3. 解决方法

动态规划方法：

1. 初始化一个数组 dp，其中 dp[0] = 1，表示空树。
2. 使用递推公式计算 dp[i]，即根据左子树和右子树的组合方式来更新 dp 数组。
3. 最终 dp[n] 即为 n 个节点构成的不同二叉搜索树的数量。

伪代码：

initialize dp array with dp[0] = 1
for i from 1 to n:
    for j from 1 to i:
        dp[i] += dp[j-1] * dp[i-j]
return dp[n]

4. 进一步优化

• 空间优化：由于每个 dp[i] 只依赖于之前的状态，因此我们已经使用最小的空间来存储这些状态。
• 时间复杂度：动态规划的时间复杂度为 O(n^2)，适合处理中等规模的输入。

5. 小总结

• 问题思路：通过递归地构建左子树和右子树，利用动态规划的思想，可以高效计算不同二叉搜索树的数量。
• 核心公式：状态转移方程 dp[i] = \sum_{k=1}^{i} dp[k-1] \times dp[i-k]，每次通过左子树和右子树的组合方式进行计算。

以上就是不同的二叉搜索树问题的基本思路。

Python代码

class Solution:
    def numTrees(self, n: int) -> int:
        # 初始化dp数组，dp[i]表示i个节点能构成的不同二叉搜索树的数量
        dp = [0] * (n + 1)
        dp[0] = 1  # 空树也是一种二叉搜索树
        
        # 动态规划计算每个dp[i]的值
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        
        return dp[n]  # 返回n个节点能构成的不同二叉搜索树的数量

Python代码解释

1. 初始化：定义一个 dp 数组，dp[i] 表示 i 个节点能构成的不同二叉搜索树的数量。初始值 dp[0] = 1，表示空树。
2. 动态规划递推：使用状态转移公式更新 dp 数组，每次根据左子树和右子树的组合方式来累加。
3. 返回结果：返回 dp[n]，即 n 个节点可以构成的不同二叉搜索树的数量。

C++代码

class Solution {
public:
    int numTrees(int n) {
        // 初始化dp数组，dp[i]表示i个节点能构成的不同二叉搜索树的数量
        vector<int> dp(n + 1, 0);
        dp[0] = 1;  // 空树也是一种二叉搜索树

        // 动态规划计算每个dp[i]的值
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];  // 返回n个节点能构成的不同二叉搜索树的数量
    }
};

C++代码解释

1. 初始化：定义一个 dp 数组，dp[i] 表示 i 个节点能构成的不同二叉搜索树的数量。初始值 dp[0] = 1，表示空树。
2. 动态规划递推：使用状态转移公式更新 dp 数组，每次根据左子树和右子树的组合方式来累加。
3. 返回结果：返回 dp[n]，即 n 个节点可以构成的不同二叉搜索树的数量。

总结

• 核心思路：通过递归构建不同的左子树和右子树，利用动态规划求解不同二叉搜索树的数量。每一个根节点的左子树和右子树的组合数相乘即为该根节点对应的不同二叉搜索树的数量。
• 时间复杂度：时间复杂度为 O(n^2)，适合处理中等规模的输入。
• 动态规划应用：该问题展示了动态规划在树形结构问题中的应用，通过递推和组合的方式有效解决了求解二叉搜索树数量的问题。