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 dfs(1,n);14     }15     vector<TreeNode *> dfs(int l,int r)16     {17         vector<TreeNode *> res;18         if(l > r)19         {20             res.push_back(NULL);21             return res;22         }23         vector<TreeNode *> left;24         vector<TreeNode *> right;25         for(int cur = l ; cur <= r  ; ++cur)26         {27             left = dfs(l,cur-1);28             right = dfs(cur+1,r);29             for(int i = 0 ; i < left.size() ; ++i)30             {31                 for(int j = 0 ; j < right.size() ; ++j)32                 {33                     TreeNode *root = new TreeNode(cur);34                     root->left = left[i];35                     root->right = right[j];36                     res.push_back(root);37                 }38             }39         }40         return res;41     }42 };