[Binary Tree][Medium] 105. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description

 

Q. Preorder와 Inorder 순회 결과 배열로 tree를 구성하라. 

 

Solution. 

 Tree 구성파트의 좋은 문제. 

 pre order는 self(mid), left, right 순서대로 traverse 하므로, tree를 해당 순서대로 visit 하는 그대로의 배열 결과가 된다. 

 따라서 depth first search 하면서 self, left, right를 배열 순서대로 값이 tree에 매칭하면 된다. 

 

 하지만 이것으로는 많은 다양한 트리가 만들어 질수 있으므로, 여기서 inorder traverse 정보를 더한다. 

 inorder는 left, self(mid), right 의 순서대로 방문한다. 

 

 두 정보를 같이 사용하기 위해, inorder 배열을 파티션 정보로 활용하면 되는데, 

 즉, 어디서 child node를 더 attach하지 않고 끊을지 결정하는 정보로 활용한다.

 

 정리된 내용을 바탕으로 코드를 작성해 본다. 

 

 

    TreeNode* buildTree_BT(vector<int>& preorder, map<int, int>& mapInorder, int& idx, int left, int right)
    {
        // valid 하지 않은 위치값은 걸러낸다.
        if (left > right)	return NULL;
        if (idx < 0 || idx >= preorder.size())
            return NULL;
        
        int value = preorder[idx++];
        // 이 node값이 가진 mid 위치를 얻는다.
        int mid = mapInorder[value];

        TreeNode* node = new TreeNode(value);
        node->left = buildTree_BT(preorder, mapInorder, idx, left, mid-1);
        node->right = buildTree_BT(preorder, mapInorder, idx, mid+1, right);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        // 값과, 위치의 정보로 inorder를 map으로 재구성한다.
        map<int, int> mapInorder;
        for (int q = 0; q < inorder.size(); ++q)
            mapInorder[inorder[q]] = q;

        int idx = 0;
        TreeNode* root = buildTree_BT(preorder, mapInorder, idx, 0, mapInorder.size()-1);
        return root;
    }

 

결과.

 

 

Note :

 tree를 구성법에 대한 좋은 문제. 

 preorder 대신 postorder와 inorder가 문제로 주어질 수도 있다. 

이때는 postorder를 뒤에서 부터 순회하면 된다. 

풀이법 숙지 필요. 

 

Note 2:

 recursive func에 index 가 reference type으로 전달되는 것에 주의. 내부적으로 index가 node 생성이 진행됨에 따라 증가해야 하며, 그 값 반영을 잃지 않기 위해 reference type으로 전달 한다.