azl397985856 commented 1 year 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

snmyj commented 1 year ago

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

    }
};

chenming-cao commented 1 year ago

解题思路

分治。根据二叉搜索树的性质，二叉搜索树的子树也为二叉搜索树。对于一个节点数为i的二叉搜索树，我们可以先选定一个节点为根，其余i - 1个节点可以分别拆成两个子二叉搜索树，按照乘法原理我们将两个子树的不同种类数相乘，即可得到当前子树分配情况下二叉搜索树的种类数，然后我们考虑所有拆分可能，相加合并结果，最终即可得到节点数为i的二叉搜索树的不同种类数。因为计算时我们要知道所有比i小的二叉搜索树的种类数，所以建立memo数组trees来储存以前结果减少重复计算。注意起始条件，节点数为0的二叉搜索树个数为trees[0] = 1。

代码

class Solution {
    public int numTrees(int n) {
        // use a memo array to save previously calculated results
        int[] trees = new int[n + 1];
        // base case：there is only one unique tree for a tree with no node
        trees[0] = 1;
        // fill in the memo array
        for (int i = 1; i <= n; i++) {
            // calculate the number of non-root nodes
            int nonroot = i - 1;
            // divide these non-root nodes into two BST, 
            // one with j nodes, one with k = nonroot - j nodes
            for (int j = 0; j <= nonroot / 2; j++) {
                int k = nonroot - j;
                // k == j, number of nodes in left tree is equal to 
                // the number of nodes in right tree, we cannot swap left and right trees
                // use multification rule to calculate total number of different trees
                // then use addition rule to add them up
                if (k == j) trees[i] += trees[k] * trees[j];
                // k != j, we can swap left and right trees, so times 2
                else trees[i] += 2 * trees[k] * trees[j];
            }
        }
        return trees[n];
    }
}

复杂度分析

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

mayloveless commented 1 year ago

思路

顶点有n种可能，左边子树要比i小，右边要大，可能性为（i -1）* （n- i）

代码

var numTrees = function(n) {
    const map = {
        0: 1,
        1: 1,
    };
    var count = (n) => {
        if (map[n]) return map[n];
        let res = 0
        for (let i = 1; i<= n; i++) {
            res += count(i - 1) * count(n - i)
        }
        map[n] = res;
        return res
    }

    return count(n)
};

复杂度

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

Abby-xu commented 1 year ago

思路

DP

代码

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()

复杂度

...

参考：https://blog.csdn.net/u012501459/article/details/46622501

buer1121 commented 1 year ago

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

    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]

Elsa-zhang commented 1 year ago

# 96. 不同的二叉搜索树
'''  动态规划
    假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
    G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
    当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i, 则 
    f(i) = G(i-1)*G(n-i)
    综合两个公式可以得到 卡特兰数 公式
    G(n)=G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
'''

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):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

bookyue commented 1 year ago

code

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

    private int dfs(int n, int[] dp) {
        if (n == 0 || n == 1) return 1;

        if (dp[n] != 0) return dp[n];

        int count = 0;
        for (int i = 1; i <= n; i++) {
            count += dfs(i - 1, dp) * dfs(n - i, dp);
        }

        dp[n] = count;
        return count;
    }

A-pricity commented 1 year ago

/**
 * @param {number} n
 * @return {number}
 */
const numTrees = (n) => {
  const 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 - 1; j++) {
      dp[i] += dp[j] * dp[i - j - 1];
    }
  }
  return dp[n];
};

klspta commented 1 year ago

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

JancerWu commented 1 year ago

虽然做过的题，但是这次总算能完全自己写出来了，记忆化搜索，直接dp还是想不到

class Solution {
    int[] f = new int[20];
    public int numTrees(int n) {
        if (n == 0 || n == 1) return 1;
        if (f[n] != 0) return f[n]; 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += numTrees(i) * numTrees(n-1-i);
        }
        f[n] = ans;
        return ans;
    }

}

paopaohua commented 1 year ago

 class Solution {
        /*
        dp[i] = i个不同的数组成的二叉搜索数的个数
        假设 i = 5
        当根节点等于 1 时 ，其余数字都比1大，只能在右边 dp[i] += dp[4]
        当根节点等于 2 时，左边有一个1比2小，右边有三个比2大的数字 dp[i] += dp[1] * dp[3]
        当根节点等于 3 时，左边有两个数比3小，右边有两个数比3大的数字 dp[i] += dp[2] * dp[2]
        ...
        知道根节点等于5，左边有4个数字比5小，只能放在5的左边,dp[i] += dp[4]
         */
        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++) {
                    int leftNum = dp[j - 1];
                    int rightNum = dp[i - j];
                    dp[i] += leftNum * rightNum;
                }
            }
            return dp[n];
        }
    }

Alexno1no2 commented 1 year ago


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]

whoam-challenge commented 1 year ago

lass 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]

tiandao043 commented 1 year ago

思路

排列组合左边子树比顶点 i 小，右边大计算累加和 i*（n-i-1）

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

class Solution {
public:
    int numTrees(int n) {
        // G(n): 长度为 nn 的序列能构成的不同二叉搜索树的个数。
        // F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数(1≤i≤n)。
        // G(n)= i=1∑n F(i,n)
        // F(i,n)=G(i−1)⋅G(n−i)
        // G(n)= i=1∑n G(i−1)⋅G(n−i)
        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];
    }
};

Elon-Lau commented 1 year ago

排列组合左边子树比顶点 i 小，右边大计算累加和 i*（n-i-1）

class Solution { vector vis; int dp(int n){ if(vis[n])return vis[n]; int ans=0; for(int i=0;i<n;++i)ans+=dp(i)*dp(n-i-1); return vis[n]=ans; } public: int numTrees(int n) { vis.assign(n+1,0); vis[0]=1; return dp(n); } }; class Solution { public: int numTrees(int n) { // G(n): 长度为 nn 的序列能构成的不同二叉搜索树的个数。 // F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数(1≤i≤n)。 // G(n)= i=1∑n F(i,n) // F(i,n)=G(i−1)⋅G(n−i) // G(n)= i=1∑n G(i−1)⋅G(n−i) vector 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];
}

};

AtaraxyAdong commented 1 year ago

class Solution {

    private HashMap<Integer, Integer> hashMap;

    public int numTrees(int n) {
        hashMap = new HashMap<>(n + 1);
        hashMap.put(1, 1);
        hashMap.put(0, 1);
        return dp(n);
    }

    public int dp(int n) {
        if (hashMap.containsKey(n)) return hashMap.get(n);
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += dp(i - 1) * dp(n - i);
        }
        hashMap.put(n, res);
        return res;
    }
}

Jetery commented 1 year ago