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

[Zoeyzyzyzy]

class Solution {
    //Leetcode 涂涂画画
    // TC：O(n^2) SP: O(n)
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        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];   
    }
}

[RestlessBreeze]

code

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 - 1 - j];
            }
        }
        return dp[n];
    }
};

[Diana21170648]

思路

分治

class Solution:
    visited = dict()

def numTrees(self, n: int) -> int:
     if nin self. Visited:
         return self.visited.get(n)
     if n <= 1:
        return 1
     res = 0
     for iin range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
      self. Visited[n] = res
      return res

**复杂度分析**
- 时间复杂度：O(N^2)，。
- 空间复杂度：O(N)

[Meisgithub]

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

[Abby-xu]

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

[kangliqi1]

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

[harperz24]

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

        for i in range(2, n + 1):
            # 枚举根节点的位置 j（其值在 1~i 之间）
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]

        return dp[-1]

        # time: O(n ** 2)
        # space: O(n)

[Hughlin07]

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

}

[NorthSeacoder]

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    //dp[i]:以 1...i为节点组成的搜索二叉树的数量
    const dp = new Array(n + 1).fill(0);
    //dp[i]=dp[j-1]*dp[i-j](j:遍历1-i)
    dp[1] = 1;
    dp[0] = 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]
};

[bookyue]

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

    private int[][] memo;

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

    private int dfs(int lo, int hi) {
        if (lo > hi) return 1;

        if (memo[lo][hi] != 0) return memo[lo][hi];

        int res = 0;
        for (int mid = lo; mid <= hi; mid++) 
            res += dfs(lo, mid - 1) * dfs(mid + 1, hi);

        memo[lo][hi] = res;
        return res;
    }

[Lydia61]

96. 不同的二叉搜索树

思路

数学方法

代码

class Solution {
public:
    int numTrees(int n) {
        long long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)C;
    }
};

复杂度分析

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

[X1AOX1A]

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

[joemonkeylee]

思路

dp

代码

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

复杂度分析

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

[bingzxy]

代码

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

复杂度分析

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

[DragonFCL]

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

[Jetery]

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

[JasonQiu]

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

    def numTrees(self, n: int) -> int:
        if n in self.dp:
            return self.dp[n]
        if n == 0 or n == 1:
            return 1
        result = 0
        for i in range(1, n + 1):
            result += self.numTrees(i - 1) * self.numTrees(n - i)
        self.dp[n] = result
        return result

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

[FireHaoSky]

思路：动态规划

代码：python

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

复杂度分析：

"""
时间复杂度：o(n)
空间复杂度：O(1)
"""

[yingchehu]

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

[snmyj]

class Solution {
public:
    int numTrees(int n) {
        int c=1;
        for(int i=0;i<n;i++)
         c = c * 2*(2*i+1)/(i+2);
         return c;

    }
};

[tzuikuo]

思路

分治

代码

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        if(n==1) return 1;
        if(n==2) return 2;
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
                //cout<<"i="<<i<<" "<<dp[j-1]*dp[n-j]<<endl;
            }
        }
        return dp[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];
    }
}

复杂度分析

• 时间复杂度：O(N^2)，其中 N 为二叉搜索树的节点个数。
• 空间复杂度：O(N)

[kofzhang]

思路

递归，分治

复杂度

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

代码

class Solution:
    @cache
    def numTrees(self, n: int) -> int:
        if n==0 or n==1:
            return 1
        s = 0
        for i in range(1,n+1):
            s += self.numTrees(i-1)*self.numTrees(n-i)
        return s

[lp1506947671]

Python3 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

复杂度分析

• 时间复杂度：一层循环是 N，另外递归深度是 N，因此总的时间复杂度是 O(N^2)
• 空间复杂度：递归的栈深度和 visited 的大小都是 N，因此总的空间复杂度为 O(N)

[DragonFCL]

var findKthLargest = function (nums, k) {
    let K = nums.length - k;
    let start = 0, end = nums.length - 1;

    while (start < end) {
        let p = partition(nums, start, end);
        if (p === K) {
            return nums[p];
        } else if (p < K) {
            start = p + 1
        } else {
            end = p - 1;
        }
    }
    return nums[start];
};

function partition(nums, start, end) {
    let pivot = nums[start];
    while (start < end) {
        while (nums[end] >= pivot && start < end) {
            end--;
        };
        nums[start] = nums[end];
        while (nums[start] < pivot && start < end) {
            start++;
        }
        nums[end] = nums[start];
    }
    nums[start] = pivot;
    return start;
}