【Day 68 】2023-08-16 - 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

[GuitarYs]

class Solution:
    def numTrees(self, n):
        if n == 0 or n == 1:
            return 1

        dp = [0] * (n+1)
        dp[0] = 1
        dp[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]

# 示例用法
solution = Solution()
n = 3
result = solution.numTrees(n)
print(result)

[Diana21170648]

思路

用笛卡尔积计算所有组合 用哈希表优化时间复杂度 分治

代码

class Solution:
    visited=dict()
    def numTrees(self, n: int) -> int:
        if n in self.visited:
            return self.visited.get(n)
        if n<=1:
            return 1
        ans=0
        for i in range(1,n+1):
            ans+=self.numTrees(i-1)*self.numTrees(n-i)#笛卡尔积
        self.visited[n]=ans
        return ans

复杂度分析

• 时间复杂度：O(N^2)。
• 空间复杂度：O(N),递归栈的深度和哈希表均为n

[Alexno1no2]

# 思路
# 注意是二叉排序树，因此 如果选择 i 为根节点，那么左子树共有 i - 1 个节点，右子树共有 n - i 个节点

# 1、dp[i]含义：i 个节点组成的二叉搜索树数量
# 2、当只有0个节点时，此时只有空树这一种二叉树，dp[0]=1
# 3、需要通过状态转移求得 dp[n]，分别选择1, 2, …, n为根节点，每种根节点对应的二叉树数量为其左子树数量乘以右子树数量
#     dp[n]=dp[0]∗dp[n−1]+dp[1]∗dp[n−2]+…+dp[n−1]∗dp[0]
# 4、因此需要两层循环计算 dp[n]，外层循环遍历节点个数从1到n的所有情况，内层循环计算每种根节点对应的二叉树数量并求和。转移方程如下：
# dp[i]+=dp[j]∗dp[i−j−1]
# 5、最后返回dp[−1]，即dp[n]

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

[passengersa]

代码： var numTrees = function(n) { const d = [1,1];

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

return d[n];

};

[Fuku-L]

代码

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for(int i = 2; i<=n; i++){
            for(int j = 1; j<=i; j++){
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}

[Momogir]

class Solution: def numTrees(self, n): """ :type n: int :rtype: int """ G = [0]*(n+1) G[0], G[1] = 1, 1

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

[Beanza]

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