//
// Created by 罗炳国 on 2023/8/7.
//

#ifndef PFJ_CODE18_BUILDTREE_H
#define PFJ_CODE18_BUILDTREE_H

#include "commonHeader.h"

/**
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 提示:
    1 <= inorder.length <= 3000
    postorder.length == inorder.length
    -3000 <= inorder[i], postorder[i] <= 3000
    inorder 和 postorder 都由 不同 的值组成
    postorder 中每一个值都在 inorder 中
    inorder 保证是树的中序遍历
    postorder 保证是树的后序遍历
 * */

class code18_buildTree {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> index;
        int N = inorder.size();
        for (int i = 0; i < N; i++)
            index[inorder[i]] = i;
        return process(inorder, 0, inorder.size() - 1,
                       postorder, 0, postorder.size() - 1);
    }

    TreeNode *process(unordered_map<int, int>& index, vector<int>& inorder, int l1, int r1,
                      vector<int>& postorder, int l2, int r2) {
        int nodeVal = postorder[r2];
        int ri = index[nodeVal];

        TreeNode *head = new TreeNode(nodeVal);
        head->left = process(index, inorder, l1,
                             r1 - 1, postorder, l2, l2 + ri - l1 - 1);

    }
};

#endif//PFJ_CODE18_BUILDTREE_H