【Day 68 】2024-01-22 - 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

[Chloe-C11]

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

        #dp
        '''
        dp五部曲:
        1.状态定义:dp[i]为当有i个节点时,一共可以组成的二叉搜索树数目
        2.状态转移:dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]
            可以比喻成前面一项是左子树情况数,后面一项是右子树情况数,相加即可
            即:dp[i]=∑dp[j]*dp[i-1-j],其中j∈[0,i-1]
        3.初始化:dp[0]=1,dp[1]=dp[0]*dp[0]=1
        4.遍历顺序:正序
        5.返回形式:返回dp[n]
        ''' 
        dp = [0 for _ in range(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[-1]

[snmyj]

class Solution {
public:
    int numTrees(int n) {
     vector<int> dp(n+1);
     dp[0]=1;
     dp[1]=1;
     for(int i=2;i<=n;i++)
     {
         for(int j=0;j<i;j++)
         {
             dp[i]+=dp[j]*dp[i-j-1];

         }
     }return dp[n];

        
    }
};

[EggEggLiu]

dp

代码

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

[adfvcdxv]

/**

• @param {number} n
• @return {number}
  */
  var numTrees = function(n) {
  let arr=new Array(n+1).fill(0)
  arr[0]=1
  for(let i=1;i<=n;i++){
  for(let j=1;j<=i;j++){
  arr[i]+=arr[j-1]*arr[i-j]
  }
  }
  return arr[n]
  };

[larscheng]

思路

• G(n) : 表示 长度为n的序列可构成不同的二叉搜索数的个数
• f(i,n) : 表示 以i为根，长度为n的序列可构成的二叉搜索数的个数

G(n)的值可以通过遍历所有i，以i为根节点构造二叉搜索数，累加所有二叉搜索数的总数

G(n) = f(1,n)+f(2,n)+....+f(i,n)
其中序列长度为1或者n=0时 G(0)=f(1,0)=1, G(1)=f(1,1)=1

对于f(i,n)则可通过左子数G(i-1)和右子数G(n-i)的所有组合方式计算得出

f(i,n) = G(i-1)*G(n-i)

所以

G(n) = G(1-1)*G(n-1) + G(2-1)*G(n-2) + .... + G(i-1)*G(n-i)

代码

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

复杂度

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

[Danielyan86]

class Solution:
    def numTrees(self, n: int) -> int:
        # 初始化数组 G 用于存储每个节点数对应的唯一BST的数量
        G = [0]*(n+1)
        G[0], G[1] = 1, 1  # 0个或1个节点时，只有一种唯一的BST。

        # 遍历节点数从2到n
        for i in range(2, n+1):
            # 对于每个节点数，计算唯一BST的数量
            for j in range(1, i+1):
                # 以j为根节点的唯一BST数量是左子树BST数量（G[j-1]）和右子树BST数量（G[i-j]）的乘积。
                G[i] += G[j-1] * G[i-j]

        # 最终结果是n个节点时的唯一BST数量
        return G[n]

[smallppgirl]

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]