不同的二叉搜索树

力扣96-不同的二叉搜索树 (opens new window)

本题难点在于递推公式的推导。

dp数组的含义在本题中很容易想到，就是i个节点可以构成的二叉搜索树的数量。

关于递推公式，只有一个或者两个节点的情况很好处理，关键看有3个节点的情况，首先看题目中的图片 可以发现，3个节点的情况可以具体分为三类。

1. 1作为根节点。此时二叉搜索树的数量为有两个节点时的二叉搜索树的数量。
2. 2作为根节点。此时数量为只有一个节点时的数量。
3. 3作为根节点。此时二叉搜索树的数量也是为有两个节点时的二叉搜索树的数量。

从这里可以总结一个初步的规律。dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] 即，3个节点的情况，可以从1个和2个节点推导而来。更加普适的公式

dp[i] += dp[j - 1] * dp[i - j]

其中，j从1开始遍历，一直到i。实际意义上，i表示选择哪一个节点作为根节点，而j - 1， i - j表示左右子树各有多少个节点。

初始化比较简单，只是注意，dp[0] = 1，因为涉及乘法推导。

遍历顺序自然是从前向后遍历。j从1开始，因为需要刨除根节点。

var numTrees = function(n) {
    //由i个节点构成的二叉树的数量为dp[i]
    const dp = new Array(n + 1).fill(0)
    //初始化dp数组
    dp[0] = 1
    dp[1] = 1
    for(let i = 2; i <= n; i++) {
        for(let j = 1; j <= i; j++) {
            //i个节点构成的二叉搜索树数量 = j - 1个节点构成的左子树数量 * i - j个节点构成的右子树数量
            dp[i] += dp[j - 1] * dp[i - j]
        }
    }
    return dp[n]
};