LeetCode: Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,

Given n = 3, there are a total of 5 unique BST's.

1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3 地址： 算法：动态规划，dp[i]记录有i个节点的搜索树数量，则$dp[i+1]=\sum_{j=0}^{i-1}dp[j]*dp[i-1-j]$，代码：

1 class Solution { 2 public: 3     int numTrees(int n) { 4         vector
        
          dp(n+1); 5         dp[0] = 1; 6         dp[1] = 1; 7         for(int i = 2; i <= n; ++i){ 8             int sum = 0; 9             for(int j = i-1; j >= 0; --j){10                 sum += (dp[j] * dp[i-1-j]);11             }12             dp[i] = sum;13         }14         return dp[n];15     }16 };
        

第二题：

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,

Given n = 3, your program should return all 5 unique BST's shown below.

1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3 地址： 算法：与上一题不同，本题要求构造出所有的解。用递归完成的，代码：

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
        
          generateTrees(int n) {13         TreeNode *p = NULL;14         if(n <= 0)  return vector
         
          (1,p);15         return generateSubtrees(1,n);16     }17     vector
          
            generateSubtrees(int s, int e){18         TreeNode *p = NULL;19         if(s > e)   return vector
           
            (1,p);20         if(s == e) {21             p = new TreeNode(s);22             return vector
            
             (1,p);23         }24         vector
             
               result;25 for(int i = s; i <= e; ++i){26 vector
              
                left = generateSubtrees(s,i-1);27 vector
               
                 right = generateSubtrees(i+1,e);28 for(int left_i = 0; left_i < left.size(); ++left_i)29 for(int right_i = 0; right_i < right.size(); ++right_i){30 p = new TreeNode(i);31 p->left = left[left_i];32 p->right = right[right_i];33 result.push_back(p);34 }35 }36 return result;37 }38 };