[Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal - JS

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
inorder, postorder 두 정수 배열이 주어진다.
inorder는 중위순회, postorder는 후순위순회
두 배열을 가지고 이진 트리를 반환하라.

제한조건
--------------------
- 1 <= inorder.length <= 3000
- postorder.length === inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder, postorder는 유일한 값으로 구성된다.
- postorder의 값들은 inorder에도 등장한다.

 

2. 접근 방법

접근방법
--------------------
postorder란?
left -> right -> 부모 순서로 순회한다.

inorder란?
left -> 부모 -> right 순서로 순회한다.

예시) inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

postorder의 마지막 요소가 root이다.

위 예시에선 '3'이 root이고,
오른쪽 하위 트리는 [15,7,20], 왼쪽 하위 트리는 [9] 이다.

즉, postorder = [왼쪽노드, 오른쪽노드, 루트] 이런식으로 순회한다.

이점만 유의하고 105번 문제와 동일한 방법으로 접근한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var buildTree = function(inorder, postorder) {
    const inorderHash = {};
    for (let i = 0; i < inorder.length; i++) {
        inorderHash[inorder[i]] = i
    }

    let postIndex = postorder.length - 1;
    function helper(left, right) {
        if (left > right) {
            return null;
        }
        const rootVal = postorder[postIndex--];
        const root = new TreeNode(rootVal);
        
        const rootIndex = inorderHash[rootVal];

        root.right = helper(rootIndex + 1, right);
        root.left = helper(left, rootIndex - 1);

        return root;
    }

    return helper(0, inorder.length - 1);
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(n)

 

[Leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal - JS 해당 문제와 동일한 방법으로 시간 복잡도를 개선하여 풀었다.

처음엔 시간 복잡도 개선한 방법이 떠오르지 않아 slice 방법으로 풀었다. 이 후 preorder와 postorder의 차이점을 반영하여 시간 복잡도 개선한 코드로 풀었다.

 

비슷한 문제를 풀면서 새롭게 깨달은 점은 전위 순회시에는 부모 -> left -> right 순서로 방문하여 root.left 할당 후 root.right를 할당해주었다.

하지만 후위 순회시에는 left -> right -> 부모 순으로 탐색한다. 즉, postorder의 배열 끝에서부터 부모, right, left 순서로 노드가 저장된다.

 

이진 트리 문제를 풀다보니 재귀에 대해 이해도가 쌓이는 것 같아 재밌다.