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

😎풀이

postorder는 마지막 인덱스가 루트 인덱스임을 알면 이전 문제와 동일한 방식으로 재귀호출하여 풀이가 가능하다.

/**
 * 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 {
    // 트리가 비어있는 경우 null 반환
    if (inorder.length === 0 || postorder.length === 0) {
        return null;
    }

    // postorder의 마지막 요소가 현재 서브트리의 루트
    const rootVal = postorder[postorder.length - 1];
    const root = new TreeNode(rootVal);

    // inorder에서 루트의 위치를 찾음
    const rootIndex = inorder.indexOf(rootVal);

    // inorder 배열을 루트를 기준으로 왼쪽과 오른쪽 서브트리로 분할
    const leftInorder = inorder.slice(0, rootIndex);
    const rightInorder = inorder.slice(rootIndex + 1);

    // postorder 배열도 같은 길이로 분할
    // 왼쪽 서브트리의 크기만큼 잘라냄
    const leftPostorder = postorder.slice(0, rootIndex);
    // 오른쪽 서브트리는 왼쪽 서브트리 다음부터 마지막 요소(루트) 전까지
    const rightPostorder = postorder.slice(rootIndex, postorder.length - 1);

    // 재귀적으로 왼쪽과 오른쪽 서브트리를 구성
    root.left = buildTree(leftInorder, leftPostorder);
    root.right = buildTree(rightInorder, rightPostorder);

    return root;
}