96.異なる二叉探索ツリーc++

96.異なる二叉探索ツリー
前に書いて、白さんはゼロから問題を解いて、解答会で構想を書くことができて、正しい答え、およびすべての使用した文法と知識の点
1.方法3

はどう思いますか?

は,二叉探索ツリーの特徴を利用して,n個のノードに二叉探索ツリーの種類がG(n)であると仮定すると,1をルートノード,左サブツリールートノードを0,右サブツリールートノードをG(n−1),2をルートノードと仮定すると,右サブツリールートノードをG(n−2)と仮定するので,G(n)=G(0)xG(n−1)...G(n−1)*G(0)

と導出する.

解題手順

配列を設け、配列の大きさを既知にし、式により

を求める.

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

2.方法1

はどう思いますか?

カトラン数公式を用いて

を求める

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

時間の複雑さ/空間の複雑さの分析/面接のシーンはどのように答えます

時間空間複雑度方法1:2回の循環O(N^2)、1つの配列O(N).方法二:一次循環O(N)、一つの変数O(1).

知識点と反省

二叉探索木

カトラン数