azl397985856 commented 2 years ago

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

MichaelXi3 commented 2 years ago

Idea

DP + Tree

Code

class Solution {
    // DP array element: with i number of nodes, how many unique structure it can acieve
    int[] dp;

    public int numTrees(int n) {
        dp = new int[n+1];
        dp[0] = 1; dp[1] = 1; // With 0 or 1 node, it can only achieve one unique structure

        // Filling in DP_Array
    for (int i=2; i <= n; i++) {
            int totalPosWithCurNumNode = 0;
            // List all possibilities of branching the tree into left and right
            // E.g. tree can have left 0 node, right n-1 node & left 1 node, right n-2 node, etc.
            for (int j=0; j <= i-1; j++) {
                int numleftNode = j;
                int numrightNode = i - 1 - j;
                int curTreeStrucPossi = dp[numleftNode] * dp[numrightNode];
                totalPosWithCurNumNode += curTreeStrucPossi;
            }
            dp[i] = totalPosWithCurNumNode;
        }

        return dp[n];
    }
}

Complexity

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

Yongxi-Zhou commented 2 years ago

思路

dp

代码

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

复杂度

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

ghost commented 2 years ago

class Solution:
    visited = {}
    def numTrees(self, n: int) -> int:
        if n <= 1: return 1
        if n in self.visited: return self.visited[n]

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

        self.visited[n] = res

        return res

ZacheryCao commented 2 years ago

idea

DP

Code

class Solution:
    def numTrees(self, n: int) -> int:
        seen = {}
        seen[0] = 1
        seen[1] = 1
        seen[2] = 2
        for i in range(3,n+1):
            seen[i] = 0
            for j in range(1, i+1):
                seen[i]+= seen[abs(j-i)]*seen[abs(j-1)]
        return seen[n]

Complexity:

Time: O(N^2) SPace:O(n)

JiangWenqi commented 2 years ago

C++

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;

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

currybeefer commented 2 years ago

a

currybeefer commented 2 years ago

vector visited; int numTrees(int n) { visited.assign(n+1,0); visited[0]=1; return dp(n); }

int dp(int n)
{
    if(visited[n]!=0) return visited[n];
    int res=0;
    for(int i=0;i<n;i++)
        res+=dp(i)*dp(n-i-1);
    visited[n]=res;
    return res;
}

djd28176 commented 2 years ago


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

MoonLee001 commented 2 years ago

思路

分治

代码

var numTrees = function (n) {
  let res = 0;
  let visited = {};
  const helper = (n) => {
    if (n <= 1) {
      return 1;
    }
    if (visited[n]) {
      return visited[n];
    }

    for (let i = 1; i <= n; i++) {
      res += helper(i - 1) * helper(n - i);
    }
    visited[n] = res;
    return res;
  }
  return helper(n);
}

复杂度分析

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

xingchen77 commented 2 years ago

    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

houmk1212 commented 2 years ago

思路

可以利用二叉搜索树的性质将问题转化为更小的子问题；

代码

class Solution {
   Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

    public int numTrees(int n) {
        return numTree(1, n);
    }

    public int numTree(int start, int end) {
        if (start == end || start > end) {
            return 1;
        }
        if (map.containsKey(new Pair<>(start, end))) {
            return map.get(new Pair<>(start, end));
        }
        int res = 0;
        for (int i = start; i <= end; i++) {
            res += numTree(start, i - 1) * numTree(i + 1, end);
        }
        map.put(new Pair<>(start, end), res);
        return res;
    }
}

复杂度

时间复杂度：O（N2）
时间复杂度：O（N）

ShawYuan97 commented 2 years ago

思路

二叉搜索树的定义：左子树一定小于根小于右子树

分治的思想，首先将一个有序数组从某个点分成两部分，那么自然就构成了左子树、根、右子树；
继续递归左子树、右子树，直到子树长度小于等于1 就停止递归返回1 左子树构成二叉搜索树种树和右子树构成二叉搜索树种树的笛卡儿积

关键点

二叉搜索树
笛卡尔积
剪枝

代码

语言支持：Python3

Python3 Code:


class Solution:
    visited = dict()
    def numTrees(self, n: int) -> int:
        """
        返回二叉搜索树的种数
        """
        if n in self.visited:
            return self.visited[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

复杂度分析

令 n 为数组长度。

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

wychmod commented 2 years ago

思路

dp + 分治

代码

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1,1,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        if dp[n]:
            return dp[n]

        def process(num):
            if dp[num]:
                return dp[num]
            ans = 0
            for i in range(1, num + 1):
                ans += process(i - 1) * process(num - i)
            dp[num] = ans
            return dp[num]

        return process(n)

hyh331 commented 2 years ago

Day68 思路

假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则G(n)=F(1) +F(2)+...+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)

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(n^2)
空间复杂度：O(n)

L-SUI commented 2 years ago


var numTrees = function(n) {
    let C = 1;
    for (let i = 0; i < n; ++i) {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C;
};

carterrr commented 2 years ago

class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = dp[1] = 1; // 某个节点没有左分支左分支只有一个节点都是一种情况 for(int i = 2; i < n + 1; i ++) { // 总结点数量 for(int j = 0; j < i; j++) { // 二叉树左边节点数量右边就是i- j 再减去顶点 dp[i] += dp[j] * dp[i - j - 1]; } } return dp[n]; } }

xil324 commented 2 years ago

class Solution(object):
    def __init__(self):
        self.memo = []; 

    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 0;
        self.memo = [[0 for _ in range(n+1)] for _ in range(n+1)]; 
        return self.helper(1,n);
    def helper(self, start,end):
        if start > end: 
            return 1; 
        if self.memo[start][end] != 0: 
            return self.memo[start][end]; 
        res = 0; 
        for i in range (start,end+1):
            left = self.helper(start,i-1); 
            right = self.helper(i+1, end); 
            res += left * right; 
        self.memo[start][end] = res; 
        return res;

Ellie-Wu05 commented 2 years ago

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]

参考官方题解

577961141 commented 2 years ago

96. 不同的二叉搜索树（未）

时间

题目链接

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

题目思路

题目的题解code

动态规划

PHP写法

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function numTrees($n) {
        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = $dp[1] = 1;

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

        return $dp[$n];
    }
}

时间和空间复杂度

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

freedom0123 commented 2 years ago

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

    }
}

zhishinaigai commented 2 years ago

思路

动态规划

代码

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

tensorstart commented 2 years ago

var numTrees = function(n) {
    let i = 1
    let sum = 0
    if(n == 1) 
        return 1

    while(i <= n/2) {
        if(i == 1)
            sum += numTrees(n - 1)
        else 
            sum += numTrees(i - 1) * numTrees(n - i)
        i++
    }

    sum *= 2
    if(n % 2 != 0)
        sum += Math.pow(numTrees(parseInt(n/2)), 2)
    return sum
};

Orangejuz commented 2 years ago

    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

LQyt2012 commented 2 years ago

思路

动态规划

代码

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

func numTrees(n int) int {
    G := make([]int, n+1)
    G[0], G[1] = 1, 1
    for i:=2;i<n+1;i++ {
        for j:=1;j<i+1;j++ {
            G[i] += G[j-1]*G[i-j]
        }
    }
    return G[n]
}

复杂度分析

时间复杂度：O(N*N)
空间复杂度：O(N)

zenwangzy commented 2 years ago


class Solution {
/**
    假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则G(n)=F(1) +F(2)+...+F(n)
    当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则F(i)=G(i-1) * G(n-i)
     * 1. 确定dp数组下标含义 dp[i]为i个节点可能的二叉树个数
     * 2. 递推公式 dp[i] += dp[j - 1]  * dp [i - j];卡特兰数: G(n)=G(0)*G(n-1) + G(1)*G(n-2)+....+G(n-1) * G(0)
     * 3. 初始化 dp[0] = dp[1] = 1; 初始化0node和1node;
     * 4. 遍历顺序 i: 2 - n j: 1 - i
     * 5. 推导结果;
     */
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;
        // int ans = 0;
        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];

    }
};
##comlpexity
TC:O(N^2)记忆化递归双层循环
SC:O(N)
更好理解的记忆化递归,hashmap实现
```cpp
class Solution {
    vector<int> visited;
    int dp(int n) {
        if (visited[n]) return visited[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += dp(i) * dp(n - i - 1);
        return visited[n] = ans;
    }
public:
    int numTrees(int n) {
        visited.assign(n + 1, 0);
        visited[0] = 1;
        return dp(n);
    }
};

miss1 commented 2 years ago

思路

动态规划

代码

var numTrees = function(n) {
  let res = [1];
  for (let i = 1; i <= n; i++) {
    let count = 0;
    for (let j = 1; j <= i; j++) {
      count += res[j - 1] * res[i - j];
    }
    res[i] = count;
  }
  return res[n];
};

复杂度

time: O(n²)
space: O(n)

mo660 commented 2 years ago

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 = 1; j <= i; j++)
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

revisegoal commented 2 years ago

分治

以 i 为根节点的二叉搜索树树左边有 i - 1 个节点，右边有 n - i 个节点，相乘既是以 i 为根节点的二叉搜索树个数

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public int numTrees(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int leftNum = numTrees(i - 1);
            int rightNum = numTrees(n - i);
            count += leftNum * rightNum;
        }
        map.put(n, count);
        return count;
    }
}

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

flyzenr commented 2 years ago

Code

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

linjunhe commented 2 years ago

1. 确定dp数组（dp table）以及下标的含义
  - dp[i]: 长度为i的序列（比如1到i）组成的二叉树数量
2. 确定递推公式
  - 以j为根，左子序列有j-1个节点，右子序列有i-j个节点
  - $dp[i] = \sum_{j=1}^{i} dp[j-1] * dp[i-j]$
3. dp数组如何初始化
  - dp[0]=1, dp[1]=1
4. 确定遍历顺序
  - dp[i]依赖于dp[j-1]和dp[i-j]，所以从前到后遍历
5. 举例推导dp数组
  - n=5
  i 0 1 2 3 4 5
  
  d[i] 1 1 2 5 14 42

i	0	1	2	3	4	5
d[i]	1	1	2	5	14	42

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

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

liuguang520-lab commented 2 years ago

思路

采用分治和动态规划

class Solution {
public:
vector<int> visited;
    int numTrees(int n) {
        visited.resize(n + 1,0);
        visited[0] = 1;
        return dp(n);
    }

    int dp(int n)
    {
        if(visited[n])
        {
            return visited[n];
        }
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            ans += dp(i) * dp(n-i -1);
        }
        return visited[n] = ans;
    }
};

复杂度分析

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

yangyuhuan commented 2 years ago

var numTrees = function(n) { let res = [1]; for (let i = 1; i <= n; i++) { let count = 0; for (let j = 1; j <= i; j++) { count += res[j - 1] * res[i - j]; } res[i] = count; } return res[n]; };

taojin1992 commented 2 years ago

/*
Time: O(n^2)
Space: O(n)
*/

class Solution {
    public int numTrees(int n) {
    // Write your code here.
        if (n < 0) return 0;
        if (n == 0) return 1;
        int[] dp = new int[n + 1]; // careful, deal with n == 0 first, index
        Arrays.fill(dp, -1);
        dp[0] = 1;
        dp[1] = 1;
        return helper(n, dp);
    }

    private static int helper(int n, int[] dp) {
        if (dp[n] != -1) return dp[n];

        if (n == 0 || n == 1) return 1;

        int numOfTrees = 0;

        int remain = n - 1;
        for (int left = 0; left <= remain; left++) {
                int right = remain - left;
                numOfTrees += helper(left, dp) * helper(right, dp);
        }

        dp[n] = numOfTrees;
                return numOfTrees;
    }
}

ShuqianYang commented 2 years ago


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

maggiexie00 commented 2 years ago

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]

TonyLee017 commented 2 years ago

思路

动态规划

代码

class Solution:
def numTrees(self, n: int) -> int:
    if n == 1: return 1
    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]

复杂度分析

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

xiayuhui231 commented 2 years ago

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

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

};

houyanlu commented 2 years ago

思路

dp数组的定义, dp[i]表示i个节点组成的不同二叉排序树的总数递推公式： dp[n] = dp[0] dp[i - 1] + dp[1] dp[i - 2] + dp[2] d[i - 3] + ... + dp[i - 1] dp[0];

代码


class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;

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

复杂度分析

时间复杂度：O(N * N)
空间复杂度：O(N)

zhiyuanpeng commented 2 years ago

class Solution:
    visited = {}
    def helper(self, n):
        if n <= 1:
            return 1
        if n in self.visited:
            return self.visited[n]
        ans = 0
        for i in range(1, n+1):
            ans += self.helper(n-i)*self.helper(i-1)
        self.visited[n] = ans
        return ans

    def numTrees(self, n: int) -> int:
        # for i in range(1, n+1):
        #   res = h(i)*h(n-i)
        # n=5, i=2, left 1,2 right 3,4,5 n-i
        return self.helper(n)

time O(N^2) sapce O(N)

leetcode-pp / 91alg-7-daily-check

【Day 68 】2022-06-07 - 96. 不同的二叉搜索树 #73

96. 不同的二叉搜索树

入选理由

题目地址

前置知识

题目描述

Idea

Code

Complexity

思路

代码

复杂度

idea

Code

Complexity:

C++

思路

代码

复杂度分析

思路

代码

复杂度

思路

关键点

代码

思路

代码

Day68 思路

复杂度分析

96. 不同的二叉搜索树（未）

时间

题目链接

题目思路

题目的题解code

PHP写法

时间和空间复杂度

思路

代码

思路

代码

复杂度分析

思路

代码

复杂度

分治

Code

思路

复杂度分析

思路

代码

复杂度分析

思路

代码