[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal, Medium

1. 문제

• 어떤 트리를 중위 순회한 inorder 배열과 후위 순회한 postorder 배열이 주어질 때, 이 트리를 반환하라.

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

    // postorder 배열을 이용해 Root를 알아낸다.
    let postIdx = postorder.length - 1;

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

        const node = new TreeNode(postorder[postIdx--]);

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

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

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

• 못풀었다.
• 궁금한건 각 순회 배열이 하나만 있을 때는 트리를 못만드냐? 이거였는데 만들 수는 있는데, 경우의 수가 너무 많다고 한다.
• 그래서 보통 이런 순회를 주고 트리를 구성하는 문제는 Root를 알 수 있는 순회와 구조를 알 수 있는 순회를 함께 사용해야 한다.
• 여기서 후위 순회 배열의 가장 마지막 요소는 항상 트리의 Root가 되고, 중위 순회 배열에서 해당 요소 위치의 전후로 왼쪽, 오른쪽 서브트리를 나누어 구성하면 된다.