/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> res;
if(n < 1){
return res;
}
else{
res = operating(1 , n);
return res;
}
}
vector<TreeNode*> operating(int start, int end){
vector<TreeNode*> res;
TreeNode * node = new TreeNode(0);
//树的构成是自底向上，使用动态规划和递归的思想，叶子结点是包含空节点的，空节点也在vector里占有空间
//生成最底层的空叶子节点
if(start > end){
res.push_back(NULL);
return res;
}
//用于从底部向上建立树的过程中的带值的叶子生成
else if(start == end){
node->val = start;
node->left = NULL;
node->right = NULL;
res.push_back(node);
return res;
}
else{
for(int i = start ; i <= end ; i++ ){
//对于每个区间再次进入循环的根不一样生成的左右子树也不一样。
vector<TreeNode* > left = operating(start , i-1);
vector<TreeNode* > right = operating(i+1 , end);
for(int le = 0 ; le < left.size() ; le++){
for(int ri = 0; ri < right.size() ; ri++ ){
//在生成叶子节点后的回溯过程中生成每个子树的分支节点。
TreeNode * temp = new TreeNode(i);
temp->left = left[le];
temp->right = right[ri];
res.push_back(temp);
}
}
}
//每颗子树都会放进结果的vector里
return res;
}
}
};
