[LeetCode] 107. Binary Tree Level Order Traversal II

😎풀이

bfs를 통해 queue를 활용하여 노드를 탐색하다 자식을 unshift 메서드를 통해 배열의 앞쪽부터 채워넣어 목표하는 배열 순서를 반환하면 된다.

/**
 * 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 levelOrderBottom(root: TreeNode | null): number[][] {
    // 결과를 저장할 배열
    const result: number[][] = [];
    
    // 루트가 null인 경우 빈 배열 반환
    if (!root) return result;
    
    // BFS를 위한 큐 생성
    const queue: TreeNode[] = [root];
    
    // 큐가 빌 때까지 반복
    while (queue.length > 0) {
        // 현재 레벨의 노드 개수
        const levelSize = queue.length;
        // 현재 레벨의 값들을 저장할 배열
        const currentLevel: number[] = [];
        
        // 현재 레벨의 모든 노드를 처리
        for (let i = 0; i < levelSize; i++) {
            // 큐에서 노드를 하나 꺼냄
            const node = queue.shift()!;
            // 현재 노드의 값을 현재 레벨 배열에 추가
            currentLevel.push(node.val);
            
            // 왼쪽 자식이 있으면 큐에 추가
            if (node.left) {
                queue.push(node.left);
            }
            
            // 오른쪽 자식이 있으면 큐에 추가
            if (node.right) {
                queue.push(node.right);
            }
        }
        
        // 현재 레벨의 값들을 결과 배열의 맨 앞에 추가
        // (bottom-up 순서를 만들기 위해)
        result.unshift(currentLevel);
    }
    
    return result;
}