Unique Binary Search Trees II

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
C++:
01 /**
02  * Definition for binary tree
03  * struct TreeNode {
04  *     int val;
05  *     TreeNode *left;
06  *     TreeNode *right;
07  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
08  * };
09  */
10  vector<TreeNode *> generateTreesHelper(int p, int q)
11  {
12      vector<TreeNode *> result;
13      if(p>q)
14      {
15          result.push_back(NULL);
16          return result;
17      }
18      if(p==q)
19      {
20          TreeNode* A=new TreeNode(p);
21          result.push_back(A);
22          return result;
23      }
24      for(int t=p;t<=q;t++)
25      {
26         vector<TreeNode *> left=generateTreesHelper(p, t1);
27         vector<TreeNode *> right=generateTreesHelper(t+1, q);
28         for(int i=0;i<left.size();i++)
29         {
30             for(int j=0;j<right.size();j++)
31             {
32                 TreeNode* root=new TreeNode(t);
33                 root->left=left[i];
34                 root->right=right[j];
35                 result.push_back(root);
36             }
37         }
38      }
39      return result;
40  }
41 
42 class Solution {
43 public:
44     vector<TreeNode *> generateTrees(int n) {
45         // Start typing your C/C++ solution below
46         // DO NOT write int main() function
47         return generateTreesHelper(1,n);
48     }
49 };
Advertisements
This entry was posted in Dynamic programming, Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s