题目描述

给定一个整数 n，求由节点值 1 到 n 组成的所有可能的不同二叉查找树（BST）的数量，并返回这个数量。

示例

例如，给定 n = 3，所有可能的二叉查找树如下所示：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

因此，对于 n = 3，总共有 5 种不同的二叉查找树。

解题思路

这个问题可以使用动态规划（Dynamic Programming, DP）来解决。我们可以定义一个数组 dp，其中 dp[i] 表示由节点值 1 到 i 组成的所有可能的二叉查找树的数量。

• 初始化 dp[0] = 1，因为空树也算作一种二叉查找树。
• 对于每个 i 从 1 到 n，遍历所有可能的根节点 j（从 1 到 i），并计算以 j 为根节点时左右子树可能的二叉查找树的数量。
• 根据二叉查找树的性质，左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。因此，左子树由 1 到 j-1 的节点组成，数量为 dp[j-1]；右子树由 j+1 到 i 的节点组成，数量为 dp[i-j]。
• 以 j 为根的二叉查找树的数量就是左子树和右子树的所有可能组合的数量，即 dp[j-1] * dp[i-j]。
• 将所有可能的根节点 j 的结果累加，即可得到 dp[i]。

PHP 示例代码

function numTrees($n) {
    $dp = array_fill(0, $n + 1, 0);
    $dp[0] = 1;
    $dp[1] = 1;

    for ($i = 2; $i <= $n; $i++) {
        for ($j = 1; $j <= $i; $j++) {
            $dp[$i] += $dp[$j - 1] * $dp[$i - $j];
        }
    }

    return $dp[$n];
}

// 示例调用
echo numTrees(3); // 输出 5

Python 示例代码

def numTrees(n):
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1

    for i in range(2, n + 1):
        for j in range(1, i + 1):
            dp[i] += dp[j - 1] * dp[i - j]

    return dp[n]

# 示例调用
print(numTrees(3))  # 输出 5

JavaScript 示例代码

function numTrees(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }

    return dp[n];
}

// 示例调用
console.log(numTrees(3)); // 输出 5

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法题解、数据结构详解、编程技巧等，欢迎大家访问学习。