二叉搜索树

二叉搜索树

二叉搜索树，又叫二叉排序树，它可以是颗空树，或是具有以下性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它根节点的值。

不同的二叉搜索树

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

输入：n=3
输出：5

假设n个节点存在的二叉搜索树是G(n),令f(i)为以i为根的二叉搜索树的个数，那么G(n) = f(0) + f(1) + … + f(n-1) + f(n) 当i为根节点时，左子树节点个数为i-1，右子树的节点为n-i, 那么f(i) = G(i-1) * G(n-i) G(n) = G(0)G(n-1) + G(1)G(n-2) +…+ G(n-1)*G(0)

var numTrees = function(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[3] = dp[2]dp[0] + dp[1]dp[1] + dp[0]dp[2]
            dp[i] += dp[j-1] * dp[i-j];
        }
    }
    // console.log(dp);
    return dp[n];
};