原题
字母题添加链接描述 一开始完全没有思路。。 百度看了别人的思路，对于这种递归构造的题目还是不熟，得多做做了。
这个题目难在构造出来。一般构造树都需要递归。 从1–n中任意选择一个数当做根节点，所以其左边的数字构成其左子树，右边的数字当做右子树。 因为要求出所有的子树，所以当左子树固定的时候，把所有可能的右子树都构成，然后再变换左子树。 这个代码难理解的地方在于left_nodes 和 right_nodes的求法，这个一定要结合递归的终止条件去看， 当选择的根节点的值i比left小的时候，那么其实左子树就是空了。 如果把这个理解了，那么下面的对左右子树的遍历应该也不难理解。 class Solution { public: vector<TreeNode *> generateTrees(int n) { vector<TreeNode *> res; if (n <= 0) return res; return helper(1, n); } private: vector<TreeNode *> helper(int start, int end) { vector<TreeNode *> subTree; if (start > end) { subTree.push_back(NULL); return subTree; } for (int k = start; k <= end; k++) { vector<TreeNode *> leftSubs = helper(start, k - 1); vector<TreeNode *> rightSubs = helper(k + 1, end); for (int i = 0; i < leftSubs.size(); i++) { for (int j = 0; j < rightSubs.size(); j++) { TreeNode *node = new TreeNode(k); node->left = leftSubs[i]; node->right = rightSubs[j]; subTree.push_back(node); } } } return subTree; } };转载于:https://www.cnblogs.com/ruoh3kou/p/9893418.html
