Leetcode - 105. Construct Binary Tree from Preorder and Inorder Traversal 풀이

문제

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

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

해결 아이디어

• 접근방법 -> 두 배열을 나열하고 규칙을 발견한다.
  • pro[idx]는 항상 어떤 sub-tree의 루트가 된다. 따라서 이를 기준으로 좌우 sub트리가 존재한다는 뜻.
  • 그 노드가 inorder에 어떤 index에 위치한지 찾고, 그 index를 pivot으로 왼쪽 오른쪽을 동일하게 재귀적으로 반복.
  • left right뿐만 아니라, preorder배열에서 root 노드의 index를 따로두어 재귀호출시킨다. 이 index를 계산하는것도 핵심.
  • 재귀적 반복 구간에서 아래와 같이 각 인덱스 값을 계산할 수 있다.

       3
  9       20
7  6     15 17 

[3, 9,7,6,  20,15,17]  preorder
 ^  -----   --------
    left     right
    
 l      p        r
[7,9,6, 3, 15,20,17]  inorder
        ^
 ^^^^^     ^^^^^^^^
  left       right
 
recursive with left side : (l ~ p-1)
recursive with right side : (p+1 ~ r)

the root idx of preorder's -> 
  - left side:  l + 1
  - right side: l + (p - l + 1)

• 아주 오랫동안 고민만 하고 풀지 못했던 문제. 힌트를 조금 참고했지만 해결해서 뿌듯하다.
• 거의 유사 문제로 106. Construct Binary Tree from Inorder and Postorder Traversal
  참고.

해결 O(n^2)

기본적인 재귀 풀이

class Solution {
public:
    TreeNode *build_tree(vector<int> pre, vector<int> in, int left, int right, int root_idx) {
        // left, right -> index of in
        // root_idx -> index of pre
        if (left > right) /* base case */
            return NULL;
        int pivot = left;
        /* search where is the index of root value in the inorder[] */
        for (pivot = left; pivot <= right; pivot++) // O(n)
            if (in[pivot] == pre[root_idx])
                break;
            
        TreeNode *node = new TreeNode;
        node->val = pre[root_idx];
        node->left = build_tree(pre, in, left, pivot - 1, root_idx + 1);
        node->right = build_tree(pre, in, pivot + 1, right, root_idx + (pivot - left + 1));
        return node;
    }
    
    TreeNode *buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build_tree(preorder, inorder, 0, inorder.size() - 1, 0);
    }
};

해결 O(n)

preorder[root_idx] 의 값이 inorder[]에 어디에 위치하는지 찾는 로직이, 위의 방법에서는 O(n) 으로 리니어 탐색이었다면, 이를 해시테이블을 활용해 O(1)에 찾을 수 있다. 따라서 총 시간복잡도는 O(n)이 된다.

class Solution {
    unordered_map<int, int> in_idx;
public:
    TreeNode *build_tree(vector<int> pre, vector<int> in, int left, int right, int root_idx) {
        // left, right -> index of in
        // root_idx -> index of pre
        if (left > right) /* base case */
            return NULL;

        int pivot = in_idx[pre[root_idx]]; // O(1)
            
        TreeNode *node = new TreeNode;
        node->val = pre[root_idx];
        node->left = build_tree(pre, in, left, pivot - 1, root_idx + 1);
        node->right = build_tree(pre, in, pivot + 1, right, root_idx + (pivot - left + 1));
        return node;
    }
    
    TreeNode *buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++)
            in_idx[inorder[i]] = i;
        
        return build_tree(preorder, inorder, 0, inorder.size() - 1, 0);
    }
};