nが与えられ、記憶値1が生成される...nのすべての構造に固有のBST(二叉探索ツリー).

本題はLeetCodeに由来する
--------------------------------------------------------------------------------
与えられた数字3
たとえば

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

考え方:
各数値を巡り,数値iをルートノードとすると,再帰左サブツリーは1,i−1,右サブツリーはi+1,nとなる.
次に、左サブツリーを各右サブツリーにペアリングし、右サブツリーを各左サブツリーにペアリングします.
生成された数を返します.

   int numTrees(int n) {
        if(n<=1)
            return 1;
        int sum=0;
        for(int i=1;i<=n;i++){
            int left=numTrees(i-1);
            int right=numTrees(n-i);
            sum+=left*right;
        }
        return sum;
    }

動的計画:

  int numTrees(int n) {
        if(n<=1)
            return 1;
        vector dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=n;i++){
          //  dp[i]=0;
            for(int j=1;j<=i;j++){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

すべてのツリーを返します.

  vector generateTrees(int n) {
        if(n<=0){
            return CreateTree(1,0);
        }
        return CreateTree(1,n);
    }
    vector CreateTree(int low,int high){
        vector result;
        if(low>high){
            result.push_back(NULL);
            return result;
        }
        for(int i=low;i<=high;i++){
        	vector left=CreateTree(low,i-1);    //       
        	vector right=CreateTree(i+1,high);  //       
        	//   ，       
                for(auto k:left){
                 for(auto j:right){
                    TreeNode* root=new TreeNode(i);
                    root->left=k;
                    root->right=j;
                    result.push_back(root);
                }
            }
        }
        return result;
    }