后序遍历的变体,先将左右子树的所有搭配方式到两个vector
,然后再用根节点分别与左右子树搭配:
// // Created by jt on 2020/8/23. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return TreeNode类vector */ vector<TreeNode *> generateTrees(int n) { // write code here return postOrder(1, n); } vector<TreeNode *> postOrder(int left, int right) { vector<TreeNode *> res; if (left > right) return vector<TreeNode *>{nullptr}; for (int i = left; i <= right; ++i) { vector<TreeNode *> leftVec = postOrder(left, i-1); vector<TreeNode *> rightVec = postOrder(i+1, right); for (int j = 0; j < leftVec.size(); j++) { for (int k = 0; k < rightVec.size(); k++) { // 根节点建立必须在循环内部 TreeNode *root = new TreeNode(i); root->left = leftVec[j]; root->right = rightVec[k]; res.push_back(root); } } } return res; } };