LeetCode/solutions/106. Construct Binary Tree from Inorder and Postorder Traversal.md

106. Construct Binary Tree from Inorder and Postorder Traversal

思路

根据中序遍历和后序遍历构建二叉树。
其实和105题（根据中序遍历和前序遍历构建二叉树）是类似的，由于后序遍历的最后一个肯定是根，所以原二叉树的根节点可以知道，然后由于树中没有相同元素， 所以我们可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。 其中在中序遍历中定位根节点可以通过hash（即unordered_map）实现。

C++

class Solution {
private:
    TreeNode* helper(int num, vector<int>& postorder, int post_last, 
        vector<int>& inorder, int in_start, 
        unordered_map<int, int>& mp){
        if(num == 0) return NULL;
        int val = postorder[post_last];
        TreeNode *node = new TreeNode(val);
        int i = mp[val] - in_start; // i代表左子树有多少个节点
        node -> left = helper(i, postorder, post_last - num + i, inorder, in_start, mp);
        node -> right = helper(num-i-1, postorder, post_last-1, inorder, 
                               in_start+i+1, mp);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int>mp;
        // 用mp记录某个节点在中序遍历数组中的索引
        for(int i = 0; i < inorder.size(); i++) mp[inorder[i]] = i;
        int num = postorder.size();
        return helper(num, postorder, num - 1, inorder, 0, mp); 
        
    }
};