【Day 68 】2024-01-22 - 96. 不同的二叉搜索树

[larscheng]

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

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