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

😎풀이

inorder와 preoder의 특성에 대해 알아야 풀이할 수 있는 문제이다.

preorder는 i번째 노드가 root 노드가 될 수 있는 순서이며

inorder는 i번째를 기준으로 좌측 인덱스의 노드는 좌측 노드, 우측 인덱스의 노드는 우측 노드이다.

/**
 * 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 {
    // 빈 배열이면 null 반환
    if (preorder.length === 0 || inorder.length === 0) {
        return null;
    }
    
    // Map을 사용하여 inorder 배열의 값과 인덱스를 저장
    // 이를 통해 값의 위치를 O(1) 시간에 찾을 수 있음
    const inorderMap = new Map<number, number>();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    
    // 실제 트리를 구축하는 재귀 함수
    function buildTreeHelper(
        preStart: number,  // preorder 배열의 시작 인덱스
        preEnd: number,    // preorder 배열의 끝 인덱스
        inStart: number,   // inorder 배열의 시작 인덱스
        inEnd: number      // inorder 배열의 끝 인덱스
    ): TreeNode | null {
        // 범위가 유효하지 않으면 null 반환
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        
        // preorder의 첫 번째 요소는 항상 현재 서브트리의 루트
        const rootVal = preorder[preStart];
        const root = new TreeNode(rootVal);
        
        // inorder에서 루트의 위치를 찾음
        const rootIndex = inorderMap.get(rootVal)!;
        
        // 왼쪽 서브트리의 노드 개수 계산
        const leftSubtreeSize = rootIndex - inStart;
        
        // 재귀적으로 왼쪽과 오른쪽 서브트리를 구축
        root.left = buildTreeHelper(
            preStart + 1,                  // 왼쪽 서브트리의 preorder 시작
            preStart + leftSubtreeSize,    // 왼쪽 서브트리의 preorder 끝
            inStart,                       // 왼쪽 서브트리의 inorder 시작
            rootIndex - 1                  // 왼쪽 서브트리의 inorder 끝
        );
        
        root.right = buildTreeHelper(
            preStart + leftSubtreeSize + 1, // 오른쪽 서브트리의 preorder 시작
            preEnd,                         // 오른쪽 서브트리의 preorder 끝
            rootIndex + 1,                  // 오른쪽 서브트리의 inorder 시작
            inEnd                           // 오른쪽 서브트리의 inorder 끝
        );
        
        return root;
    }
    
    // 초기 호출
    return buildTreeHelper(0, preorder.length - 1, 0, inorder.length - 1);
}