【Day 68 】2024-06-14 - 96. 不同的二叉搜索树

[azl397985856]

96. 不同的二叉搜索树

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/unique-binary-search-trees/

前置知识

• 二叉搜索树
• 分治

  题目描述

  
  给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

[Martina001]

时间复杂度 O(n^2) 空间复杂度On

public int numTrees(int n) {
            // 没想到吧 这是一个递归题，当n=5 root为3时，左子树为1和2构成，右子树由45构成，可能的结果就是count(1,2)*count(3,4)
            // 递归记得加备忘录
            memo = new int[n+1][n+1];
            return traverse(1, n);
        }

        int memo[][];

        private int traverse(int start, int end) {
            if (start > end) {
                return 1;
            }
            if(memo[start][end] != 0){
                return memo[start][end];
            }
            int res = 0;
            for (int i = start; i <= end; i++) {
                // 以当前i节点为root的时候的情况：
                int leftCount = traverse(start, i - 1);
                int rightCount = traverse(i + 1, end);

                res += leftCount * rightCount;
            }
            memo[start][end] = res;
            return res;
        }

[luzhaofeng]

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1

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

[Dtjk]

class Solution { public: int numTrees(int n) { vector dp(n + 1, 0); dp[0] = 1; 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];
}

};

[pandapls]

状态转移方程 想要计算有 i 个节点的不同 BST 的数量。假设我们选择 j 作为根节点（1 <= j <= i） 那么： 左子树 的节点个数是 j - 1，因为左子树的节点都比根节点 j 小 右子树 的节点个数是 i - j，因为右子树的节点都比根节点 j 大

所以 ： dp[j - 1] 表示左子树的不同 BST 数量 dp[i - j] 表示右子树的不同 BST 数量

··· 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[i] += dp[j -1] * dp[i - j]
    }
}

return dp[n]

}; ··· 时间 O(n2) 空间 O(n)

[hillsonziqiu]

代码

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    let G = []
    G.length = n + 1;
    G.fill(0);
    G[0] = G[1] = 1;

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

复杂度分析

• 时间复杂度：O(n^2)；
• 空间复杂度：O(n)；

[lxy1108]

记忆化递归

class Solution:
    @lru_cache(None)
    def numTrees(self, n: int) -> int:
        if n<=1:
            return 1
        rs = 0
        for i in range(1,n+1):
            rs+=self.numTrees(i-1)*self.numTrees(n-i)
        return rs

[CathyShang]

class Solution:
    def numTrees(self, n: int) -> int:
        f = [0] * (n+10)
        f[0] = 1
        for i in range(1, n + 1):
            for j in range(1, i+1):
                f[i] += f[j-1] * f[i-j]

        return f[n]

• Time $O(n^{2})$
• Space $O(n)$