unique binary search tree I&II

unique binary search tree I&II

I dynamic problem

dp[i] means the amount of unique binary search tree that formed by i elements.So, dp[i] = sum(dp[j]*dp[i-j]) and j is from 0 to i-1 and means the elemtnts of nodei's left child tree.

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

II a little hard

While problem I is solved, problem II seems not hard. For a interval[a,b],enumerate the root of the tree. Build the left child tree and right child tree using the left elements and right elements. Connect each kind of the left and right and push it into result and recursive.

 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<TreeNode *> generateTrees(int n) {
13         return build(1,n);
14     }
15     
16     vector<TreeNode* > build( int start, int end ) {
17         vector<TreeNode* > result;
18         if ( start > end ) {
19             result.push_back(NULL);
20             return result;
21         }
22         for ( int i = start; i <= end; i++ ) {
23             vector<TreeNode* > resultLeft = build(start,i-1);
24             int ll = resultLeft.size();
25             vector<TreeNode* > resultRight = build(i+1,end);
26             int rl = resultRight.size();
27             for ( int j = 0; j < ll; j++ ) {
28                 for ( int k = 0; k < rl; k++ ) {
29                     TreeNode* node = new TreeNode(i);
30                     node->left = resultLeft[j];
31                     node->right = resultRight[k];
32                     result.push_back(node);
33                 }
34             }
35         }
36         return result;
37     }
38     
39 };

Loading Disqus comments...
Table of Contents