从中序与后序遍历序列构造二叉树-力扣

• 中序遍历序列存放节点的顺序是左中右，后序遍历存放节点的顺序是左右中
• 后序遍历序列的最后一个节点即为二叉树的根节点
• 由于每个值在二叉树中都是唯一的，那么根据根节点的值，就可以将中序遍历序列一分为二，前部分存储的是根节点左子树的节点，后半部分存储的是根节点右子树的节点
• 不论中序还是后序遍历，左右子树的节点是相同的，那么就可以将两个序列划分为四个序列，中序遍历序列的左右部分，后序遍历序列的左右部分
• 那么此时，以根节点的值构造根节点，根节点的左子节点，就可以以中序遍历序列的左部分和后序遍历序列的左部分进行构造，右子节点同理
• 那么递归下去，就能够构造完成整棵二叉树
• 注： 在实现时，对 inorderleft 等四个数组未进行初始化，规定数组的大小，此时是无法 inorderleft[i] = inorder[i]; 这样去赋值的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* subVec(vector<int> inorder, vector<int> postorder){
        if(inorder.empty() && postorder.empty()){
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[postorder.size() - 1]);
        if(postorder.size() == 1){
            return root;
        }
        int flag = 0;
        for(flag; flag < inorder.size(); flag++){
            if(inorder[flag] == root->val){
                break;
            }
        }
        vector<int> inorderleft;
        vector<int> inorderright;
        vector<int> postorderleft;
        vector<int> postorderright;
        for(int i = 0; i < flag; i++){
            inorderleft.push_back(inorder[i]);
            postorderleft.push_back(postorder[i]);
        }
        for(int j = flag; j + 1 < inorder.size(); j++){
            inorderright.push_back(inorder[j + 1]);
            postorderright.push_back(postorder[j]);
        }

        root->left = subVec(inorderleft, postorderleft);
        root->right = subVec(inorderright, postorderright);

        return root;
        
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        TreeNode* root = subVec(inorder, postorder);
        return root;

    }
};