【Day 68 】2021-11-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

[yanglr]

思路:

基于二叉搜索树的特性, 用动态规划求解。需要用分治的是LeetCode95. 不同的二叉搜索树II吧。

方法: 动态规划

dp数组的选取

dp[i]: 以 i 为根节点value的不同的可能的二叉搜索树的个数

[1, 2, ... i ... n]

选取中间的任意结点i 作为根结点, 由于是二叉搜索树, 它的左子树所属的区间是: [1 … i-1], 它的右子树所属的区间是: [i+1, n]。

那么原区间被分隔成下面这个样子:

[1, i-1] i [i+1, n]

当根节点root的值为i时, 根据组合原理可知能形成的二叉树的种类为: f(i-1)f(n-(i+1) + 1) = f(i-1) f(n-i)

即: c(i) = f(i-1) * f(n-i)

而题目要求给定一个n, 让求出1~n总共能组成多少个bst?

那就是求和一下, 就是最终要求的答案。

f(i) = sum( f(k-1) * f(i-k)), i: [1, n], k: [0, i-1]

代码:

实现语言: C++

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = 1; // root == null的树, 只有1棵
        for (int i = 1; i <= n; i++)
        {
            for (int k = 0; k <= i-1; k++)
            {
                dp[i] += dp[k] * dp[i - 1 - k];
            }
        }
        return dp[n];
    }
};

复杂度分析:

• 时间复杂度: O(n^2), 其中n是节点的个数
• 空间复杂度: O(n)

[ysy0707]

思路：动态规划

class Solution {
    public int numTrees(int n) {
        //动态规划
        //dp[i]代表的是当前数有i个数的时候有几种情况
        int dp[]=new int[n+1];
        //没有数字 算作一种
        dp[0]=1;
        //只有一个数字算作一种
        dp[1]=1;

        for (int i = 2; i <=n; i++) {
            for (int j = 0; j < i; j++) {
                //i表示的是总的个数 j表示的是左子树分的个数 
                //左子树最多为i-1 因为根还要一个节点
                //左边分 j 个 那右边就分i-j-1个
                dp[i]+=dp[j]*dp[i-j-1];

            }
        }
        return dp[n];

    }
}

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

[zhangzz2015]

思路

• 先思考二插搜索树的特点，左边的小于root，右边的大于root，考虑dp，定义 dp(x) 为有x 个数情况下有多少种二插搜索树的组合，可以转化为 选择1 作为root ，[2 x] 作为1 的右子树有多少种组合， 2 作为root，1 在左子树的，[3 x] 作为右子树有多少种组合，两个相乘，因此递推的关系为 dp(n) = sum (i, dp[i-1]*dp[n-i]) 要注意，形成搜索树的数值并不关键， [ 2 3 4] 形成的搜索树的组合和 [ 3 4 5] 形成的组合是相同的，关键的是 连续数的个数。时间复杂度为O(n^2)，空间复杂度为O(n)

关键点

代码

• 语言支持：c

c Code:

class Solution {
public:
    int numTrees(int n) {

        //  dp(n) = sum(i   dp[i-1] * dp[n - i]) 

        vector<int> dp(n+1, 1); // from 1 to n. 

        for(int i=1; i<=n; i++)
        {
            int sum =0; 
            for(int j=1; j<=i; j++)
            {
                sum += dp[j-1] * dp[i-j];
            }
            dp[i] = sum; 
        }

        return dp[n]; 

    }
};

[joriscai]

思路

• 整数 1 - n 中的 k 作为根节点值，则 1 - k-1 会去构建左子树，k+1 - n 会去构建右子树，从而形成二叉树
• 以 k 为根节点的 BST 种类数 = 左子树 BST 种类数 * 右子树 BST 种类数

代码

javascript

/*
 * @lc app=leetcode.cn id=96 lang=javascript
 *
 * [96] 不同的二叉搜索树
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
  // 如果整数 1 - n 中的 k 作为根节点值，则 1 - k-1 会去构建左子树，k+1 - n 会去构建右子树。
  // 左子树出来的形态有 a 种，右子树出来的形态有 b 种，则整个树的形态有 a * b 种。
  //    以 k 为根节点的 BST 种类数 = 左子树 BST 种类数 * 右子树 BST 种类数
  // 问题变成：不同的 k 之下，等号右边的乘积，进行累加。

  const G = new Array(n + 1).fill(0)
  G[0] = 1
  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]
};
// @lc code=end

复杂度分析

• 时间复杂度：O(n^2)，两层循环遍历
• 空间复杂度：O(n)，存放所有节点的情况

[kidexp]

thoughts

memorized search + divide and conquer

对于每个root从1 遍历到n，然后计算左右子树的不同个数 相乘就得到root节点对应的二叉搜索树的个数， 最后相加

code

from collections import defaultdict

class Solution:
    def numTrees(self, n: int) -> int:
        dp = defaultdict(int)
        dp[0] = dp[1] = 1

        def memorized_search(num_nodes):
            if num_nodes in dp:
                return dp[num_nodes]
            for j in range(1, num_nodes + 1):
                dp[num_nodes] += memorized_search(j - 1) * memorized_search(
                    num_nodes - j
                )
            return dp[num_nodes]

        return memorized_search(n)

complexity

Time O(n^2)

Space O(n)

[chang-you]

class Solution {
    public int numTrees(int n) {

    int[] res = new int[n + 1];
    res[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            res[i] += res[j] * res[i - j - 1];
        }
    }
    return res[n];
    }
}

[RocJeMaintiendrai]

思路

f(n) = f(0) f(n - 1) + f(1) f(n-2) + ... + f(n - 2) f(1) + f(n - 1) f(0)

代码

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

复杂度分析

时间复杂度

O(n)

空间复杂度

O(n)

[biancaone]

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

        # i代表总数，从2算到n
        # j代表左子树节点个数，从0到i - 1
        for i in range(2, n + 1):
            for j in range(0, i):
                dp[i] += (dp[j] * dp[i - j - 1])

        return dp[n]

[erik7777777]

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
//time O(n^2) space O(n)

[tongxw]

思路

动态规划，dp(i)是n个节点的BST数量，显然dp(1) = 1 dp(2)，当1为根时，2挂在1的右侧，dp(2) = dp(1)，当2为根时，1挂在2的左侧，dp(2) += dp(1) dp(3),同上，分类讨论123为根，有dp(3) = dp(2) + dp(1) dp(1) + dp(2) 综上dp(i) = sum(dp(j-1) dp(i-j)) 1 <= j <= i 为了统一计算，假设dp(0) = 1

代码

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

      return dp[n];

    }
}

• TC: O(n^2)
• SC: O(n)

[xinhaoyi]

class Solution { public int numTrees(int n) { //直接用dfs递归就行 return dfs(1,n); }

//我们保证 left是左边起始点，right是右边最大点
public int dfs(int left, int right){
    int count = 0;
    //出口
    if(left >= right){
        return 1;
    }
    //取点
    for(int i = left; i <= right; i++){
        count += dfs(left,i-1) * dfs(i+1,right);
    }
    return count;
}

}

[wangzehan123]

Java Code:

class Solution {
    static int[] cache = new int[20];

        public int numTrees(int n) {
            if (n <= 1) {
                return 1;
            }

            if (cache[n] > 0) {
                return cache[n];
            }

            int ret = 0;
            for (int i = 0; i < n; i++) {
                /**
                 * 每个点轮聊作为顶点，那么左右子树的可能性相乘，就是每个点作为顶点的可能性
                 */
                ret += numTrees(i) * numTrees(n - 1 - i);
            }

            cache[n] = ret;
            return ret;
        }
}

[heyqz]

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 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]

time complexity: O(n^2) space complexity: O(n)

[JiangyanLiNEU]

Idea

• Memorization

  Python

  class Solution(object):
  def numTrees(self, n):
      memo = {}
      def update(left, right):
          memo[(left,right)] = 0
          if left >= right:
              memo[(left,right)] += 1
          else:
              for i in range(left, right+1):
                  if (left, i-1) not in memo:
                      update(left, i-1)
                  if (i+1, right) not in memo:
                      update(i+1, right)
                  memo[(left, right)] += memo[(left,i-1)]*memo[(i+1, right)]
      update(1, n)
      return memo[(1,n)]

  JavaScript

  var numTrees = function(n) {
  let memo = new Map();
  const compute = (cur) => {
     if( cur ==1 || cur == 0) return 1;
     if(memo.has(cur)) return memo.get(cur);
     let res = 0; 
     for(let g=1; g<=cur; g++){
       res = res + (compute(g-1) * compute(cur-g));
     } 
     memo.set(cur, res);
     return res;  
  }
  return compute(n);    
  };

[ginnydyy]

Problem

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

Notes

• DP + Divide and conquer
• Given n numbers, if choose index k as the root, then the number of the BSTs for the given n numbers is the number of BSTs for the numbers [0, k -1] multiply the number of BSTs for the numbers [k + 1, n - 1].
• So dp[n] = dp[k] * dp[n - k -1] when k is the root index. Here n is the total of given numbers. k is the number of numbers on the left side of the root, n - k - 1 is the number of numbers on the right side of the root.
• Thus, we need to consider all the cases for different k, and accumulate the products, that will be the answer for dp[n]. And k could be [0, n - 1].
• The base cases is dp[0] = 1 and dp[1] = 1, to reach dp[n], we also need to consider all the cases for different i (total of the numbers), i could be [0, n].
• Therefore, the problem can be solved by iterating through i [0, n] and k [0, i - 1] to process all the possible total of numbers and possible BSTs for each total.

Solution

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1]; // dp[i] means given i numbers, the total number of unique BSTs
        dp[0] = 1; // when there is no number to choose, then there is only one possible BST
        dp[1] = 1; // when there is only one number to choose, then there is only one possible BST

        for(int i = 2; i <= n; i++){ // given i numbers
            for(int j = 0; j < i; j++){ // iterate through all the root indices for possible BSTs, j is the root index
                dp[i] += dp[j] * dp[i - j - 1]; // the number of possible BSTs is the procut of the number of possible BSTs on the left of the root and the number of the possible BSTs on the right of the root, and need to accumulate all the cases with all possible root indices. j is the number of nums on left side, i - j - 1 is the number of nums on right side.
            }
        }

        return dp[n];
    }
}

Complexity

• Time: O(n^2). n is the number of the numbers. We need to iterate through 0 to n, and in each iteration, we need to iterate through all the possible root indices. So overall O(n^2).
• Space: O(n). Extra space is needed for the dp array, and its size is n + 1, so overall is O(n).

[pan-qin]

Idea:

DP. The number of BST only depends on the number of elements in the BST, rather than which element they are. Let dp array store the number of BST with input n. Base case is dp[1]=1, dp[0]=1. For an input n, any number i in the range [1...n] can be the root. If i is the root, the left side has i-1 nodes, which can form dp[i-1] BSTs; the right side has n-i nodes, which can form dp[n-i] trees. Since the trees formation is independent, in total when root is i, there are dp[i-1]*dp[n-i] trees. Therefore dp[n] is the sum of trees formed by each i.

Complexity:

Time: O(n^2). Space: O(n).

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

[st2yang]

思路

• dp

代码

• python

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

复杂度

• 时间: O(n^2)
• 空间: O(n)

[yingliucreates]

link:

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

代码 Javascript

const numTrees = function(n) {
    return factorial( 2 * n ) / ( factorial( n + 1 ) * factorial( n ) );
};

function factorial( num ){
    if( num <= 0 )
        return 1;
    else
        return num * factorial( num - 1 );
}

[leungogogo]

• Java

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if (i == 1) {
                dp[i] = 1;
            } else {
                for (int j = 1; j <= i; ++j) {
                    if (j == 1 || j == i) {
                        dp[i] += dp[i - 1];
                    } else {
                        dp[i] += (dp[j - 1] * dp[i - j]);
                    }
                }
            }
        }

        return dp[n];
    }
}

Time: O(n^2)

Space: O(n)

[sxr000511]

const numTrees = function(n) { return factorial( 2 n ) / ( factorial( n + 1 ) factorial( n ) ); };

function factorial( num ){ if( num <= 0 ) return 1; else return num * factorial( num - 1 ); }

[okbug]

var numTrees = function(n) {
    let 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];
};

[yan0327]

思路： 第一个不足的点是没有考虑清楚二叉搜索树的性质=》这题的本质是大题化小题，从小答案推答案 其次就是避免重复计算=》要么用动态规划的数组保存对应的数目，要么用记忆化递归【本质都是存储已计算的值】 =》笛卡尔积 乘 对于n中的i节点:

for x:=0;x<i;x++｛
     count += s[i]*s[n-i-1]
｝

动态规划
func numTrees(n int) int {
    dp := make([]int,n+1)
    dp[0] = 1
    for i:=1;i<=n;i++{
        for j:=0;j<=i-1;j++{
            dp[i] += dp[j]*dp[i-j-1]
        }
    }
    return dp[n]
}

记忆化递归
func numTrees(n int) int {
    memo := make([]int,n+1)
    var helper func(n int, memo *[]int) int
    helper = func(n int, memo *[]int) int{
        if n==1 || n == 0{
            return 1
        }
        if (*memo)[n] > 0{
            return (*memo)[n]
        }
        count := 0
        for i:=0;i<=n-1;i++{
            count += helper(i,memo) * helper(n-i-1,memo)
        }
        (*memo)[n] = count
        return count
    }
    return helper(n,&memo)
}

时间复杂度O（n²） 空间复杂的O（n）

[shawncvv]

思路

分治法

代码

Python Code

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
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        self.visited[n] = res
        return res

复杂度

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

[zszs97]

开始刷题

题目简介

【Day 68 】2021-11-16 - 96. 不同的二叉搜索树

题目思路

• 动态规划

题目代码

代码块

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];
    }
};

复杂度

• 时间复杂度 O(n2)
• 空间复杂度 O(n)

[MonkofEast]

96. Unique Binary Search Trees

Click Me

Algo

1. The quetion is the exactly "the product of BST for (left) and (right) (divide the set into 2 parts)"

Code

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
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        self.visited[n] = res
        return res

Comp

T: O(N^2)

S: O(N)

[mannnn6]

代码

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];
    }
}

复杂度

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

[nonevsnull]

思路

• 拿到题的直觉解法
  • 每个node都可以当作root-断点，从而考虑其左边和右边的nodes，当作branches
  • 递归下去，左边branch有多少种情况，右边branch有多少种情况，最后会决定当前root的最终unique count
  • 因为左右分步，取乘法；

AC

代码

class Solution {
    // int total;
    public int numTrees(int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1, 1);
        map.put(0, 1);
        return dp(n, map);
    }

    public int dp(int n, HashMap<Integer, Integer> map){
        if(map.containsKey(n)) return map.get(n);
        int total = 0;
        for(int i = 1;i <= n;i++){
            int l = dp(i - 1, map);
            map.put(i - 1, l);
            int r = dp(n - i, map);
            map.put(n - i, r);
            total += l * r;
        }

        return total;
    }
}

复杂度

time: O(N^2) space: O(N)

[pophy]

思路

• 记忆化递归

Java Code

class Solution {
    int[][] memo;
    public int numTrees(int n) {
        memo = new int[n + 1][n + 1];
        return helper(1, n);
    }

    private int helper(int start, int end) {
        if (start < 0 || start > end || start == end) {
            return 1;
        }
        if (memo[start][end] != 0) {
            return memo[start][end];
        }
        int count = 0;
        for (int i = start; i <= end; i++) {
            count += helper(start, i - 1) * helper(i + 1, end);
        }
        return memo[start][end] = count;
    }
}

时间&空间

• 时间 O(n^2)
• 空间 O(n^2)

[jocelinLX]

刚开始学习，借鉴了力扣狗大王的代码：

class Solution:
    def numTrees(self, n: int) -> int:
        store=[1,1] #构建f(0)和f(1)
        if n <=1:
            return store[n]
        for i in range(2,n+1):
            s=i-1
            res=0
            for j in range(i):
                res+=store[j]*store[s-j]
            store.append(res)
        return store[n]

[BlueRui]

Problem 96. Unique Binary Search Trees

Algorithm

• This can be solved as a dynamic programming problem using recursion.
• Let dp[i] represent the number of unique BSTs with n nodes. Then dp[i] = sum of dp[j-1] dp[i-j]* where j = [1, i].

Complexity

• Time Complexity: O(N²).
• Space Complexity: O(N).

Code

Language: Java

public int numTrees(int n) {
    // Let dp[i] represent the number of unique BSTs with n nodes.
    // Then dp[i] = sum of dp[j-1] * dp[i-j] where j = [1, i].
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            // Let j be the index of the root node.
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

[ZacheryCao]

Idea

DP. DP[i] the number of unique BST with number i as the root. Transit function DP[i] = sum(DP[j-1] * DP[i-j]) j = 1...i

Code

class Solution:
    def numTrees(self, n):
        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]

Complexity:

Time: O(N^2) Space: O(N)

[shamworld]

var numTrees = function(n) {
    let 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];
};

[XinnXuu]

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

[chun1hao]

var numTrees = function (n) {
  let dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  // 使用 i 个数字构建，去除掉根节点后，转化为子问题：左子树 j(0——i-1)个数字构建、右子树 i-1-j 个数字构建
  for (let i = 2; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      dp[i] += dp[j] * dp[i - j - 1];
    }
  }
  return dp[n];
};

[Francis-xsc]

思路

动态规划

代码

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

复杂度分析

• 时间复杂度：O(N^2)，其中 N 为数组长度。
• 空间复杂度：O(N)

[wenlong201807]

代码块

var numTrees = function (n) {
  // 备忘录的值初始化为 0
  let memo = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
  let count = (lo, hi) => {
    // base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，
    // 虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0
    if (lo > hi) return 1;
    if (memo[lo][hi] != 0) return memo[lo][hi];
    let res = 0;
    for (let i = lo; i <= hi; i++) {
      // i 的值作为根节点 root
      let left = count(lo, i - 1);
      let right = count(i + 1, hi);
      // 左右子树的组合数乘积是 BST 的总数
      res += left * right;
    }
    memo[lo][hi] = res;
    return res;
  };
  // 计算闭区间 [1, n] 组成的 BST 个数
  return count(1, n);
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[GZ712D]

思路

dp

代码

class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 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]  

time complexity: O(n^2)
space complexity: O(n)

[littlemoon-zh]

dfs + memo

class Solution:
    def __init__(self):
        self.mem = {}

    def numTrees(self, n: int) -> int:

        if n in self.mem: return self.mem[n]
        if n <= 1: return n
        s = 0
        for i in range(1, n+1):
            a = self.numTrees(i-1) 
            b = self.numTrees(n-i)
            if a == 0: a = 1
            if b == 0: b = 1

            s += a * b
        self.mem[n] = s
        return s

[lilixikun]

思路

dp

代码

var numTrees = function(n) {
    let dp = new Array(n+1).fill(0)
    dp[0] = 1
    dp[1] = 1
    for(let i = 2;i<=n;i++){
        for(let j = 0;j<i;j++){
            dp[i]+=dp[j]*dp[i-j-1]
        }
    }
    return dp[n]
};

复杂度

• 时间复杂度 O(n*n)
• 空间复杂度 O(1)

[BpointA]

思路

带记忆的分治

Python代码

class Solution:
    memo={0:1}
    def numTrees(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]
        ans=0
        for i in range(n):
            left=i
            right=n-i-1
            ans+=self.numTrees(left)*self.numTrees(right)
        self.memo[n]=ans
        return ans

[liuyangqiQAQ]

class Solution {
    public int numTrees(int n) {
        //根据动态规划
        /*
        令i为根节点是的个数f(n)。则G(n) 也就是搜索节点的个数为:
        G(n) = f(1) + f(2) + f(3) + ... + 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)
         */
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j < i + 1; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

[zhy3213]

思路

打表+动规

代码

    def numTrees(self, n: int) -> int:
        b=[1,1,2,5]
        if n<4:
            return b[n]
        for i in range(4,n+1):
            tmp=0
            for j in range(i):
                tmp+=b[i-j-1]*b[j]
            b.append(tmp)
        return b[-1]

[watermelonDrip]

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

超时，有重复计算

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[0] = 1 # 空树也是合法的

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

[Victoria011]

思路

从 1-n, 每个数都可以作为 root. 当选择 i 来作为 root 时, 1 ~ i-1 会在左子树 i+1 ~ n 会在右子树。假设 G(n) 是n个数能组成的所有bst个数, F(i, n) 是i 为root 时1~n能组成的bst个数，那么 G(n) 则为 F(i, n) i=1...n 之和。而F(i,n) = G(i-1) G(n-i) 左右两子树的组合个数。结合两个函数得到: G(n) = G(i-1)G(n-i) i=1...n 之和

代码

class Solution:
    def numTrees(self, n):
        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]

复杂度分析

Time Complexity: O(N^2) 两个for循环。

Space Complexity: O(N) 用了一个list G.

[CoreJa]

思路

虽然写作"分治"，但其实读作动规23333.

这个题分治的思路倒是很清晰：

• 遍历1到n，取i
• 把0到i-1，i+1到n分成两棵树，这里注意两棵树本质没区别，可能的排列只和长度有关(即0到i-1的节点数)
• 两边分别递归，把结果相乘，遍历到最后的累加值就是答案

当然，真要是朴素分治就铁超时了，所以回溯法+备忘录即可，留一个数组来保存不同输入的分治法

也可以动规去找，方法是一样的。代码给了三种方法

代码

class Solution:
    def numTrees1(self, n: int) -> int:
        def divide(tree, dp):
            ans = 0
            for i in range(1, tree + 1):
                left = dp[i - 1] if dp[i - 1] else divide(i - 1, dp)
                right = dp[tree - i] if dp[tree - i] else divide(tree - i, dp)
                ans += left * right
            dp[tree] = ans
            return ans

        return divide(n, [1, 1, 2] + [0] * (n - 2))

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

    def numTrees(self, n: int) -> int:
        ans = 1
        for i in range(n):
            ans = ans * 2 * (2 * i + 1) / (i + 2)
        return ans

[15691894985]

【Day 68】96. 不同的二叉搜索树

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

思路动态规划: dp[n]长度为n的二叉树个数 f(i,n)是以i为根节点，n为长度的二叉树个数

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] *(n+1)
        dp[0]= 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]

复杂度分析：

时间复杂度：O(n*n) n为二叉树的节点个数

空间复杂度：O( n) dp记录的空间

分治递归调用,用hashmap来优化，记录以及访问节点的种类数

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*n) 递归深度为n，外面一层n

空间复杂度：O( n) 递归深度和visited

[ninghuang456]

class Solution {
    public int numTrees(int n) {
         int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++)
            for(int j = 1; j < i + 1; j++) 
                dp[i] += dp[j-1] * dp[i-j];

        return dp[n];

    }
}
Time: O(n^2)
Space: O(n)

[HWFrankFung]

Codes

var numTrees = function(n) {
    var f = [1];
    var i = 1;
    while (i<=n) {
        var j = 0;
        f[i] = 0
        while (j<i) {
            f[i]+= f[j] * f[i - j - 1];
            j++;
        }
        i++;
    }
    return f[n];
};

[learning-go123]

思路

• 分治+备忘录

代码

• 语言支持：Go

Go Code:

func numTrees(n int) int {
    memo := make([]int, 1920)
    var count func(int, int) int
    count = func(lo, hi int) int {
        if lo > hi {
            return 1
        }
        if memo[lo*100+hi] != 0 {
            return memo[lo*100+hi]
        }
        res := 0
        for i := lo; i <= hi; i++ {
            res += count(lo, i-1) * count(i+1, hi)
        }

        memo[lo*100+hi] = res
        return res
    }
    return count(1, n)
}

复杂度分析

令 n 为数组长度。

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

[ghost]

题目

96. Unique Binary Search Trees

思路

Divide and conquer

代码

class Solution:
    def numTrees(self, n: int) -> int:
        visited = {}
        return self.helper(n, visited)

    def helper(self, n, visited):
        if n <= 1: return 1
        if n in visited: return visited[n]

        res = 0
        for i in range(1, n+1):
            res += self.helper(i-1, visited) * self.helper(n-i, visited)

        visited[n] = res

        return res    

复杂度

Space: O(n) Time: O(n*n)