算法思路

该题做法与 LeetCode 105. 从前序与中序遍历序列构造二叉树 一模一样，建议先点击链接观看上篇题解。

中序遍历的顺序左 -> 根 -> 右，后序遍历的顺序为左 -> 右 -> 根

1. 先找到根节点，后序遍历的最后一个数即为根节点
2. 利用哈希表，找到根节点在中序遍历中的位置k，位置k左边的序列为其左子树的中序遍历，右边的序列为右子树的中序遍历
3. 如果位置k左边的序列长度为l，则在后序遍历中，从区间左端点到后面的l个数为左子树的后序遍历，剩下的为右子树的前序遍历
4. 根据左右子树的前序遍历和中序遍历，再递归求解，最后将根节点与左右子树拼接起来

C ++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> hash;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i ++) hash[inorder[i]] = i;
        return dfs(inorder, postorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr)
    {
        if (pl > pr) return NULL;

        int val = postorder[pr];
        int k = hash[val];
        int len = k - il;

        auto root = new TreeNode(val);
        root -> left = dfs(inorder, postorder, il, k - 1, pl, pl + len - 1);
        root -> right = dfs(inorder, postorder, k + 1, ir, pl + len, pr - 1);

        return root;
    }
};