[이진 트리 (Binary Tree)] LC #107 Binary Tree Level Order Traversal II

문제 설명

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

문제 링크: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

1. 문제의 핵심: BFS 레벨 순회와 결과 뒤집기

이 문제는 표준적인 '이진 트리 레벨 순회(Level Order Traversal)' 문제에서 출력 순서만 바꾼 버전입니다. 레벨 순회는 너비 우선 탐색(BFS)을 사용하여 구현하는 것이 정석입니다.

핵심 아이디어: BFS를 사용하여 트리를 위에서 아래(top-down) 순서로 순회하고, 각 레벨의 노드들을 리스트에 담는다. 모든 레벨의 탐색이 끝나면, 최종 결과 리스트의 순서를 뒤집어 아래에서 위(bottom-up) 순서로 만든다.

2. 해결 전략

  1. 최종 결과를 담을 `List>`와 노드를 처리할 `Queue`를 생성합니다.
  2. 루트 노드가 `null`이면 빈 리스트를 즉시 반환합니다. `null`이 아니면 큐에 추가합니다.
  3. 큐가 비어있지 않은 동안 반복문을 실행합니다.
    • 현재 레벨의 노드 수(levelSize)를 큐의 현재 크기로 저장합니다.
    • 현재 레벨의 노드 값들을 담을 `currentLevel` 리스트를 생성합니다.
    • levelSize만큼 반복하여 큐에서 노드를 꺼내(poll) 그 값을 `currentLevel`에 추가하고, 해당 노드의 왼쪽/오른쪽 자식이 있다면 큐에 추가(offer)합니다.
    • 내부 반복문이 끝나면 완성된 `currentLevel`을 최종 결과 리스트에 추가합니다.
  4. 모든 순회가 끝나면, `Collections.reverse()`를 사용하여 결과 리스트의 순서를 뒤집어줍니다.
  5. 뒤집힌 리스트를 반환합니다.

3. Java 코드 구현

import java.util.*;

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) return result;

        Queue queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List currentLevel = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);
                if (currentNode.left != null) queue.offer(currentNode.left);
                if (currentNode.right != null) queue.offer(currentNode.right);
            }
            result.add(currentLevel);
        }

        Collections.reverse(result);
        return result;
    }
}

💡 코드 세부 포인트