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

 

confused what "{1,#,2,3}" means? 

 

Hide Tags

   

 

---

　　这个嘛，对于1 to n ，如果要用某个值做节点，那么这个值左部分的全部可能的树，递归调用获得，右部分同理，这样便可以获取结果。

 

#include 
      
       #include 
       
        using namespace std;/** * Definition for binary tree */struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:    vector
        
          generateTrees(int n) {        return help_f(1,n);    }    vector
         
           help_f(int l,int r)    {        vector
          
            ret;        if(l>r){            ret.push_back(NULL);            return ret;        }        for(int i=l;i<=r;i++){            vector
           
             lPart = help_f(l,i-1); vector
            
              rPart = help_f(i+1,r); for(int lidx=0;lidx
             
              left = lPart[lidx]; pNode->right = rPart[ridx]; ret.push_back(pNode); } } } return ret; }};int main(){ return 0;}