[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

문제 부터 요약하면

Preorder traversal과 Inorder traversal 결과가 주어질 때, 해당 결과 두개를 사용해 binary tree를 만드는 문제였습니다.

 

<Solution>

Preorder traversal는 root, left subtree, right subtree를 탐색하고, Inorder traversal은 left subtree, root, right subtree를 탐색합니다. 

 

이것을 바탕으로 한 기본 아이디어는 다음과 같습니다.

1. Preorder traversal의 첫번째 원소를 root로 뽑아낸다. 2. 해당 root 값을 Inorder traversal의 결과에서 찾아 left, right subtree로 구분한다.  3. 2의 과정에서 찾은 left, right subtree의 원소 갯수를 통해 Preorder traversal의 left, right subtree도 구분한다. 4. 1-3의 과정을 Preorder, Inorder left subtree 그리고 Preorder, Inorder right subtree에 대해 반복한다.

 

예시를 통해 조금 더 살펴보면, 

Input : preorder -> [3, 9, 20, 15, 7] / inorder-> [9, 3, 15, 20, 7]

첫번째 1~3의 과정을 하게되면, 순서대로 아래의 결과를 알게 됩니다.

 

root : 3

inorder left subtree : 9

inorder right subtree : 15, 20, 7

preorder left subtree : 9

preorder right subtree : 20, 15, 7

 

이렇게 알게 된 결과에 대해 재귀적으로 tree를 build하면 됩니다. (다음 순서는 inorder left subtree와 preorder left subtree에 대해 1~3의 과정 진행)

 

현재 1~3의 과정을 진행할 때, preorder traversal의 첫번째 원소를 inorder traversal 결과에서 쭉 스캔하며 찾으면 시간 복잡도가  최악의 경우 O(n) 이므로 전체 알고리즘의 경우 O(n^2)의 시간복잡도가 걸립니다. 

 

해당 과정을 줄일 수 있는데, unordered map을 활용하여 inorder traversal의 값과 index를 저장해둠으로써 스캔하며 찾는 과정의 복잡도를 O(1)로 줄일 수 있습니다. 이렇게 하면 전체 알고리즘을 O(n)으로 구현이 가능합니다.

 

해당 과정을 구현한 것의 코드는 아래와 같습니다. 

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

struct arr_with_size{
    int * arr;
    int total_element;  
};

class Solution {
public:
    // for fast search make unordered map to save index of inorder traversal
    unordered_map <int, int> inordermap;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // for fast search make unordered map to save index of inorder traversal
        for(int i = 0; i<inorder.size(); i++){
            inordermap[inorder[i]] = i;
        }

        // change vector to array
        arr_with_size pre_arr = {&preorder[0], static_cast<int>(preorder.size())};
        arr_with_size in_arr = {&inorder[0], static_cast<int>(inorder.size())};

        return buildTree_recursive(pre_arr, in_arr);
    }

    // recursive build
    TreeNode* buildTree_recursive(arr_with_size& preorder, arr_with_size& inorder){

        // if there is no element return NULL
        if(preorder.total_element == 0) return NULL;

        // first element of preorder array is root
        TreeNode* node = new TreeNode;
        node->val = *preorder.arr;

        // find root index on current array
        int r_index = inordermap[*preorder.arr] - inordermap[*inorder.arr];

        // divide left right by using root index and inorder
        arr_with_size left_inorder = {inorder.arr, r_index};
        arr_with_size right_inorder = {inorder.arr + r_index + 1, inorder.total_element - (r_index+1)};

        // divide left right by size got from inorder
        arr_with_size left_preorder = {preorder.arr+1, left_inorder.total_element};
        arr_with_size right_preorder = {preorder.arr+1+left_preorder.total_element, right_inorder.total_element};

        node->left = buildTree_recursive(left_preorder, left_inorder);
        node->right = buildTree_recursive(right_preorder, right_inorder);


        return node;
    }

};