[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal, Medium

1. 문제

• 트리를 전위순회한 배열 preorder와 중위순회한 inorder 배열이 주어질 때, 해당 이진 트리를 반환하라.

2. 해결

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    // 특정 값의 인덱스를 빠르게 파악하기 위한 Map.
    const map = new Map<number, number>();
    inorder.forEach((val, index) => map.set(val, index));

    // preorder 배열을 이용해 Root를 알아낸다.
    let preIdx = 0;

    function build(leftIdx, rightIdx) {
        if(leftIdx > rightIdx) return null;

        const node = new TreeNode(preorder[preIdx++]);

        // inorder 배열을 이용해 왼쪽 서브트리, 오른쪽 서브트리를 나누고 재귀 구성.
        const targetIdx = map.get(node.val);

        node.left = build(leftIdx, targetIdx-1);
        node.right = build(targetIdx+1, rightIdx);

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

• 106번 문제와 같다.
• 여기서 주의해야 할 점은 전위 순회 배열은 앞에서 부터 루트 노드를 찾아야 하고, 다음으로 오는 서브 트리는 왼쪽 서브트리이므로 node.left를 먼저 구성해주어야 한다.