1.问题

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

2.思路

        使用中序和后序构造二叉树，需要根据二者的特性进行区间分割，然后不断递归直到构造完成。

实现步骤如下：

        1.判断两个数组是否为空，为空直接返回nullptr；

        2.通过后序遍历找到根节点的值。

        3.通过根节点的值找到中序遍历根节点的下标。

        4.根据根节点下标将中序遍历数组分为左右两个数组（左右两个子树的中序遍历）

        5.根据数组长度的一致性，求得后序遍历的左右两个数组（左右子树的后序遍历）

        6.递归处理左右数组。

        （使用前序和中序构造二叉树步骤与上边是相同的）

3.代码实现

  TreeNode* traversal(vector<int>& inorder,int inorderBegin,int inorderEnd,
                        vector<int>& postorder,int postorderBegin,int postorderEnd)
    {
        //1.判断是否为空
        if(postorderBegin==postorderEnd) return nullptr;
        //2.获取根节点
        int rootValue = postorder[postorderEnd-1];
        TreeNode* root = new TreeNode(rootValue);

        if(postorderBegin-postorderEnd==1) return root;
        //3、找到中序遍历中根节点的下标
        int delimeterIndex = 0;
        for(delimeterIndex = inorderBegin;delimeterIndex<inorderEnd;delimeterIndex++){
            if(inorder[delimeterIndex]==rootValue) break;
        }
        //4、分割中序遍历数组
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimeterIndex;
        int rightInorderBegin = delimeterIndex+1;
        int rightInorderEnd = inorderEnd;
        //5.分割后序遍历数组
        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin+leftInorderEnd-leftInorderBegin;
        int rightPostorderBegin = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd-1;
        //6、递归处理左右区间
        root->left = traversal(inorder,leftInorderBegin,leftInorderEnd,postorder,  leftPostorderBegin,leftPostorderEnd);
        root->right = traversal(inorder,rightInorderBegin,rightInorderEnd,postorder,rightPostorderBegin,rightPostorderEnd);

        return root;
    }