[Leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal - JS

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

 

1. 문제 분석

문제분석
--------------------
preorder, inorder가 주어질 때, 이진 트리를 구성하여 반환하라.
preorder는 선순서 순회, inorder는 중위 순회이다.

제한조건
--------------------
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder와 inorder는 고유한 값으로 구성됩니다.
- inorder의 각 값은 preorder에도 나타납니다.
- preorder은 트리의 선순서 순회가 보장됩니다.
- inorder는 트리의 중위 순회가 보장됩니다.

 

2. 접근 방법

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

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

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

Q. inorder에서 두번째 요소가 첫번째의 부모노드인지 어떻게 알았는가?

만약, root의 left값이 9 - 10 이렇게 있었다면
inorder는 [10,9,3 ...] 이런식으로 되어 있을테니
3번째 요소가 root(부모) 요소가 되었을 것이다.

이를 코드로 풀어보면,
preorder의 첫번째 요소는 root(부모)이고
inorder에서 root를 찾아서 root 기준 서브 트리를 만든다.
    - 좌측은 중위 순회 시 부모 방문 이전 노드들 -> left inorder subtree
    - 우측은 중위 순회 시 부모 방문 이후 노드들 -> right inorder subtree

preorder 또한, 서브 트리를 만드는데,
    - 첫번째 요소(root)를 제외하여 left inorder subtree의 길이만큼 -> left preorder subtree
    - 그 이후의 나머지 요소들 -> right preorder subtree

각각 preorder, inorder에서 left, right subtree를 만들었으니
이를 재귀함수로 호출하여 그 반환값을 root.left, root.right에 할당해준다.

 

 

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(preorder, inorder) {
    if (!preorder.length || !inorder.length) return null;

    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    const rootIndex = inorder.indexOf(rootVal);

    const leftInorder = inorder.slice(0, rootIndex);
    const rightInorder = inorder.slice(rootIndex + 1);

    const leftPreorder = preorder.slice(1, leftInorder.length + 1);
    const rightPreorder = preorder.slice(leftInorder.length + 1);

    root.left = buildTree(leftPreorder, leftInorder)
    root.right = buildTree(rightPreorder, rightInorder)

    return root;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n^2) 

- 공간복잡도: O(n)

 

rootIndex를 찾을 때 마다 inorder를 탐색해야하고,

트리에 있는 모든 노드를 한번씩 방문하여 slice 분할해야하므로 시간복잡도가 O(n^2)이다.

시간 복잡도를 개선하는 방법을 알아보자.

 

 

5. 시간복잡도 개선 방법

미리 hashmap에다가 inorder 요소의 인덱스를 저장해주면 인덱스 찾는 시간 복잡도가 O(1)로 단축할 수 있다.

 

function buildTree(preorder, inorder) {
    const indexMap = {}; // inorder 배열의 값-인덱스 매핑
    inorder.forEach((val, index) => {
        indexMap[val] = index;
    });

    let preIndex = 0; // preorder 배열의 현재 인덱스

    function helper(left, right) {
        if (left > right) return null; // 기저 조건: 서브트리가 비어있음

        const rootVal = preorder[preIndex++]; // 현재 루트 값 선택
        const root = new TreeNode(rootVal);

        // inorder에서 현재 루트의 인덱스를 해시맵을 통해 찾음
        const index = indexMap[rootVal];

        // 재귀적으로 왼쪽과 오른쪽 서브트리를 구성
        root.left = helper(left, index - 1);
        root.right = helper(index + 1, right);

        return root;
    }

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

 

위와 같은 방법으로 하면 노드를 방문하는 시간만 계산하면 되므로 최종 시간복잡도 O(n)이 걸린다.