23.03.16. 풀었던 문제들

Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal

 어떤 binary tree의 inorder와 postorder 순회 결과가 주어졌을 때 tree를 구성하는 문제이다. 이 때 inorder와 postorder의 모든 element는 unique하다.

 

첫 접근 : time O($n^{2}$), space O(n)

  일단 postorder의 제일 마지막 index가 root인 것(rootidx라 하자), 그리고 inorder에서 rootidx 왼쪽의 것은 왼쪽 subtree, 오른쪽의 것은 오른쪽 subtree임을 알 수 있다. 따라서 각 탐색에서 왼쪽/오른쪽을 나누어야 한다는 것은 쉬운 직관으로 알 수 있다.

 그럼 다음 탐색에서는 postorder의 어떤 index가 root가 될까?

 

 만약 탐색 범위를 알 수 있다면 어떨까? inorder에서 [시작 범위 ~ rootidx-1]는 왼쪽 subtree, [roodix + 1 ~ 끝 범위]가 오른쪽 subtree이므로 이 두 범위의 길이를 알 수 있다. 그러면 이 길이로 postorder의 왼쪽 subtree와 오른쪽 subtree또한 나눌 수 있게 된다.

 왼쪽 subtree 길이를 leftlen, 오른쪽 subtree 길이를 rightlen이라 하면 postorder의 [시작 범위 ~ 시작범위 + leftlen - 1]은 왼쪽 subtree, [시작 범위 ~ 끝 범위 -1]은 오른쪽 subtree이다.

 따라서 각 탐색에서 inorder와 postorder의 left, right subtree를 나눌 수 있게 되었다. 정리하면 다음과 같고 이를 구현하면 된다.

• postorder 탐색 끝 index에 있는 element가 inorder의 root이다.
• inorder 탐색 시작 index, 끝 index를 이용해 leftlen, rightlen을 계산한다.
• leftlen, rightlen을 이용해 inorder와 postorder의 다음 탐색 범위를 계산한다.
• left subtree, right subtree를 recurse한다.

// Runtime 51 ms Beats 16.18%
// Memory 26.1 MB Beats 78.64%

class Solution {
public:
    vector<int> inorder, postorder;
    TreeNode* build(int inStart, int inEnd, int postStart, int postEnd){
        // 탐색 종료 조건
        if(inStart > inEnd || postStart > postEnd) return NULL;

        // postorder의 마지막 index의 element가 root이므로 inorder에서 그 값을 찾는다.
        int inRoot = -1;
        for(int i = inStart; i<=inEnd; i++){
            if(postorder[postEnd] == inorder[i]){
                inRoot = i;
                break;
            }
        }

        if(inRoot == -1) return NULL;

        TreeNode* curroot = new TreeNode(postorder[postEnd]);
        // leftlen, rightlen을 계산한다.
        int leftlen = inRoot - inStart;
        int rightlen = inEnd - inRoot;

        // left, right subtree로 recurse한다.
        curroot->left = build(inStart, inRoot-1, postStart, postStart + leftlen - 1);
        curroot->right = build(inRoot+1, inEnd, postStart + leftlen, postEnd - 1);

        return curroot;
    }
    TreeNode* buildTree(vector<int>& _inorder, vector<int>& _postorder) {
        inorder = _inorder; postorder = _postorder;
        return build(0, _inorder.size()-1, 0, _postorder.size()-1); // *** 실수 : size()를 넣었다.
    }
};

 

시간복잡도

 이렇게 풀 경우 inorder를 순회하는 과정에서 worst O(n)의 시간이 걸린다. 따라서 T(n) = 2T(n/2) + O(n)이므로 worst O($n^{2}$)이다.

 

공간복잡도

 stack은 O(h)만큼 탐색하게 된다. worst case로 1자로 길게 늘어진 tree의 경우 h == n이므로 O(n)이다. 추가 공간으로 inorder, postorder의 공간을 그대로 사용하므로 O(n)이다. 따라서 O(n)

 

 

두번째 접근 : time, space O(n)

 inorder를 순회하는 과정이 너무 길다. inorder의 모든 element가 unique이므로 이를 map을 사용해 O(logn), 또는 unordered map을 사용해 O(1)로 접근할 수 있다.

// Runtime 8 ms Beats 97.85%
// Memory 26.6 MB Beats 25.72%

class Solution {
public:
    vector<int> inorder, postorder;
    unordered_map<int, int> inorder_idx;
    TreeNode* build(int inStart, int inEnd, int postStart, int postEnd){
        if(inStart > inEnd || postStart > postEnd) return NULL;

        int inRoot = inorder_idx[postorder[postEnd]]; // 개선 : unordered_map으로 index get

        if(inRoot == -1) return NULL;

        TreeNode* curroot = new TreeNode(postorder[postEnd]);
        int leftlen = inRoot - inStart;
        int rightlen = inEnd - inRoot;

        curroot->left = build(inStart, inRoot-1, postStart, postStart + leftlen - 1);
        curroot->right = build(inRoot+1, inEnd, postStart + leftlen, postEnd - 1);

        return curroot;
    }
    TreeNode* buildTree(vector<int>& _inorder, vector<int>& _postorder) {
        inorder = _inorder; postorder = _postorder;
        // 개선 : map initialize
        for(int i = 0; i<inorder.size(); i++){
            inorder_idx[inorder[i]] = i;
        }
        return build(0, _inorder.size()-1, 0, _postorder.size()-1);
    }
};

 

시간복잡도

 이렇게 풀 경우 inorder를 순회하는 과정에서 worst O(1)의 시간이 걸린다. 따라서 T(n) = 2T(n/2) + O(1)이므로 worst O(n)이다.

 

공간복잡도

 공간복잡도는 위와 동일하다.