构建二叉搜索树ii

后序遍历的变体，先将左右子树的所有搭配方式到两个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;
    }
};