LeetCode解法汇总889. 根据前序和后序遍历构造二叉树

 目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

描述：

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示：

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

解题思路：

这题和105，106题差不多，仍然是不断构建前序和后序匹配的区间进行生成。

前序遍历中，第一个是根结点A，第二个则是子树的根结点B。这时候分两种场景，如果存在左子树，则可以根据B在后序遍历中的位置进行分割成两部分。如果不存在左子树，则只要继续分割一部分即可。

以题preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]为例：

找到子树B也就是2在postorder中的位置，就可以分成两部分，第一部分在preorder中是[2,4,5]，在postorder中是[4,5,2]。

第二部分在preorder中是[3,6,7]，在postorder中是[6,7,3]。继续遍历下去，直到节点长度为1即可。

代码：

class Solution889
{
public:
    TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder)
    {
        vector<int> indexMap(postorder.size() + 1);
        for (int i = 0; i < postorder.size(); i++)
        {
            indexMap[postorder[i]] = i;
        }
        TreeNode *node = buildNode(indexMap, preorder, postorder, 0, preorder.size() - 1, 0, postorder.size() - 1);
        return node;
    }

    TreeNode *buildNode(vector<int> &indexMap, vector<int> &preorder, vector<int> &postorder, int preStart, int preEnd, int postStart, int postEnd)
    {
        TreeNode *root = new TreeNode(preorder[preStart]);
        if (preStart == preEnd)
        {
            return root;
        }
        int expectValue = preorder[preStart + 1];
        int index = indexMap[expectValue];
        int leftLength = index - postStart + 1;
        int rightLength = postEnd - index - 1;

        if (leftLength >= 1)
        {
            root->left = buildNode(indexMap, preorder, postorder, preStart + 1, preStart + leftLength, postStart, index);
        }
        if (rightLength >= 1)
        {
            root->right = buildNode(indexMap, preorder, postorder, preStart + leftLength + 1, preEnd, index + 1, postEnd - 1);
        }
        return root;
    }
};