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

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

 

Preorder와 Inorder traverse  정보가 주어질 때, 전체 tree를 구성하라.

 

우선 InOrder와 PreOrder에 대해 다시 정리할 필요가 있다. 

 

DFS 그 순서 그대로 tree를 접근한다면, PreOrder 방식이라고 할 수 있다.

어느 노드의 child를 어떤 식으로 attach하는지 정보를 얻기 위해 InOrder가 필요하다. 

inOrder는 이 값들을 tree의 밸런스 정보와 함께 가지고 있다. 

즉, 특정 값이 inOrder에 존재 한다면, inOrder에서 해당 값보다 작은 index는 왼쪽 트리 노드로,

큰 index는 오른쪽 트리 노드로 구성된다고 보면 되겠다.

 

다시 정리하면, 

PreOrder는 DFS 노드 접근 순서, 

InOrder는 구성 정보, 즉 트리의 좌, 우를 분할케 해 준다. 

 

코드. 

TreeNode* buildTreePreIn(int& idx, vector<int>& preorder, unordered_map<int, int>& mapInorder, int left, int right)
{
    if (left > right)      // 이 끊는 정보를 얻기 위해 inOrder data가 필요.
        return nullptr;

    int val = preorder[idx++];
    int mid = mapInorder[val];

    auto leftNode = buildTreePreIn(idx, preorder, mapInorder, left, mid - 1);
    auto rightNode = buildTreePreIn(idx, preorder, mapInorder, mid+1, right);

    TreeNode* node = new TreeNode(val, leftNode, rightNode);
    return node;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
{
    unordered_map<int, int> mapInorder;
    for(int q = 0; q < inorder.size(); ++q)
        mapInorder[inorder[q]] = q;

    int idx = 0;
    return buildTreePreIn(idx, preorder, mapInorder, 0, preorder.size()-1);
}

 

결과

 

Note : 할 때마다 헛갈린 문제. 원리에 대해 제대로 이해 필요.