leetcode 96

图片.png

计算唯一二叉搜索树的个数：用到catalan公式：

图片.png

                    1                        n = 1

                2        1                   n = 2
               /          \
              1            2
  
   1         3     3      2      1           n = 3
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

n = 0 时赋为1
dp[2] = dp[0] * dp[1]　　　(1为根的情况)

 　　+ dp[1] * dp[0]　　 (2为根的情况)

同理可写出 n = 3 的计算方法：

dp[3] = dp[0] * dp[2]　　　(1为根的情况)

 　　+ dp[1] * dp[1]　　 (2为根的情况)

 　 + dp[2] * dp[0]　　 (3为根的情况)

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

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

---

leetcode 95

图片.png

• 遍历过程：

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

代码：C++

vector<TreeNode*>* DFS(int start, int end) {
    vector<TreeNode*> *ans = new vector<TreeNode*>();
    if (start > end) {
        ans->push_back(NULL);
    }
    else {
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> *leftAll = DFS(start, i - 1);
            vector<TreeNode*> *rightAll = DFS(i + 1, end);
            for (int j = 0; j < leftAll->size(); j++) {
                for (int k = 0; k < rightAll->size(); k++) {
                    TreeNode* nn = new TreeNode(i);
                    nn->left = (*leftAll)[j];
                    nn->right = (*rightAll)[k];
                    ans->push_back(nn);
                }
            }
        }
    }


    return ans;
}
vector<TreeNode*> generateTrees(int n) {
    if (n == 0)
        return {};
    return *DFS(1, n);
}

• 注意：这应该是我第一次碰到vector也要返回指针的题目，解决这个题简直耗费智商。
  leftAll 找到所有可能的子树组合，然后将left+right排列组合 计算出所有可能插入到ans 中node
• 注意
  int i = start; i <= end; i++;
  这里面不要忘记end也可以取