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

给定两个整数数组inorder和postorder，前者是二叉树的中序遍历，后者是二叉树的后序遍历，请构造并返回这棵二叉树

首先要理解二叉树的中序遍历和后序遍历的特点，后序数组的最后一个元素一定是当前子树的根节点，由于中序遍历是左右中，因此利用后序数组的最后一个元素，然后在中序数组中进行切割就可以得到当前子树的左前序数组和右前序数组，由于后序遍历是左右中，因此可以利用左前序数组和右前序数组元素个数在后序数组中切割得到左后序数组和右后序数组，然后利用这些数组递归构造当前子树的左右子树即可

代码如下：

TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
        if(postorder.size() == 0)   return nullptr;
 
        //确定根节点的值，是后序数组的最后一个元素
        int rootVal = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(rootVal);
 
        //节点是叶子节点
        if(postorder.size() == 1)   return root;
 
        //确定中序数组切割点
        int index=0;
        for(;index<inorder.size();index++){
            if(inorder[index] == rootVal)
                break;
        }
 
        //切中序数组，得到左中序数组和右中序数组
        //数组统一为左闭右开区间
        vector<int> leftInorder(inorder.begin(),inorder.begin() + index);
        vector<int> rightInorder(inorder.begin() + index + 1,inorder.end());
 
        //后序数组需要舍弃末尾元素，以便确定下一次递归的根节点
        postorder.resize(postorder.size()-1);
 
        //切割后序数组，得到左后序和右后序数组
        //数组统一为左闭右开区间
        vector<int> leftPostorder(postorder.begin(),postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(),postorder.end());
 
        //递归处理
        root->left = traversal(leftInorder,leftPostorder);
        root->right = traversal(rightInorder,rightPostorder);
 
        return root;
}

本题和力扣105 从前序与中序遍历序列构造二叉树本质上是一样的，前序数组的第一个元素是当前子树的根节点，与后序数组类似。