[LeetCode] 102. Binary Tree Level Order Traversal 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Binary Tree Level Order Traversal

---

 

문제 요약 (Binary Tree Level Order Traversal)

이진 트리가 주어졌을 때,
노드를  레벨 단위로 순서대로 탐색하여 반환하는 문제

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

Input:
    3
   / \
  9  20
     / \
    15  7

Output:
[
  [3],
  [9,20],
  [15,7]
]

---

🤔 처음 떠올린 아이디어

처음에는 이렇게 생각했다.

“DFS로 한 번 순회하면서
각 노드의 레벨(depth)을 저장하면 되지 않을까?”

그래서 다음처럼 접근하려 했다.

• 모든 노드를 순회하면서
• (노드, depth)를 기록
• depth 기준으로 그룹화

가능은 하지만,
뭔가 문제 의도에 비해 돌아가는 느낌이 들었다.

 

---

❗ 핵심 깨달음

Level Order는 사실상 BFS 문제다.

굳이 레벨을 따로 저장하지 않아도 된다.

왜냐하면, 👉 Queue의 현재 size가 곧 현재 레벨의 노드 개수이기 때문

 

이걸 깨닫는 순간 구조가 정리된다.

---

💡 핵심 아이디어: BFS + Queue

알고리즘 흐름

1. root를 큐에 넣는다.
2. 큐가 빌 때까지 반복한다.
3. 현재 큐의 size를 구한다.
   → 이것이 현재 레벨의 노드 개수다.
4. 그 개수만큼만 poll 하면서 하나의 리스트에 담는다.
5. 각 노드의 자식을 큐에 넣는다.
6. 완성된 리스트를 결과에 추가한다.

---

코드 (Java) 

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

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

        while (!queue.isEmpty()) {
            int size = queue.size(); // 현재 레벨의 노드 개수
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(level);
        }

        return result;
    }
}

 

📈 Time / Space Complexity

• Time: 모든 노드를 한 번씩 방문 → O(N)
• Space: 큐에 최대 한 레벨의 노드가 저장 → O(W)
  (W = 트리의 최대 너비, 최악의 경우 O(N))

---

 

🔹 다른 접근: DFS + depth 활용

BFS가 가장 직관적이지만, DFS로도 해결할 수 있다.

핵심은 depth를 함께 전달하는 것이다.

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) return;

        if (result.size() == depth) {
            result.add(new ArrayList<>());
        }

        result.get(depth).add(node.val);

        dfs(node.left, depth + 1, result);
        dfs(node.right, depth + 1, result);
    }
}

 

 

각 노드는 “현재 깊이(depth)”라는 정보를 가지고 있다.

depth가 곧 레벨이므로,

• result의 index = depth
• depth에 해당하는 리스트에 값 추가

이 방식도 결국 한 번의 순회(O(N))로 해결된다.

 

---

 

📝 이번 문제에서 얻은 깨달음

•  Level Order는 “트리를 어떻게 순회할까?” 문제가 아니다. 👉 “레벨 단위로 어떻게 끊을까?”가 핵심이다.
• 그리고 그 해답은 ✔️ BFS에서 queue.size()가 레벨을 자동으로 보장해준다는 것
• 트리 문제에서 “level”, “층”, “위에서 아래로” 라는 키워드가 나오면 👉 BFS를 먼저 떠올리자