Leetcode - 106. Construct Binary Tree from Inorder and Postorder Traversal

문제

어떤 이진트리의 중위순회, 후외순회한 순서가 나열된 두 배열이 주어진다. 이것으로 원래 트리를 만들어라. (단 모든 값은 유니크한 수를 갖는다.)

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

아이디어

• 기본적으로 105. Construct Binary Tree from Preorder and Inorder Traversal 문제와 거의 동일하다. 자세한 해설은 이 링크를 참고.
• 재귀 호출시 root 로 할 노드의 index를 계산 하는식이 반대이다. 아래 해당 코드를 잘 참고할것.

    [9,15,7,20,3] post
               ^
    [9,3,15,20,7] in
       ^

        node->left = gen_tree(in, post, left, pivot - 1, post_idx - (right - pivot + 1));
                                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        node->right = gen_tree(in, post, pivot + 1, right, post_idx - 1);
                                                           ^^^^^^^^^^^^

해결

class Solution {
    unordered_map<int, int> inidx;
public:

    TreeNode* gen_tree(vector<int> in, vector<int> post, int left, int right, int post_idx) {
        if (left > right)
            return NULL;
        // search post[post_idx] in in[]
        int pivot = inidx[post[post_idx]];
        TreeNode *node = new TreeNode;
        node->val = post[post_idx];
        node->left = gen_tree(in, post, left, pivot - 1, post_idx - (right - pivot + 1));
        node->right = gen_tree(in, post, pivot + 1, right, post_idx - 1);
        return node;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++)
            inidx[inorder[i]] = i;
        return gen_tree(inorder, postorder, 0, inorder.size() - 1, postorder.size() - 1);
    }
};