[LeetCode] 102. Binary Tree Level Order Traversal - Java

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal - LeetCode

---

문제

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

---

풀이

풀이 과정

이진 트리가 주어질 때, 트리의 각 레벨별 노드를 리스트로 묶어 반환하는 문제이다.

이 문제에서는 큐를 이용하여 레벨별로 노드를 구한다.

우선 반환할 결과값 리스트, 탐색에 사용할 큐를 선언하고, 빈 트리가 들어왔을 경우 탐색할 필요가 없으므로 빈 리스트를 바로 return 하도록 먼저 처리해준다.

// 반환할 결과값 리스트
List<List<Integer>> result = new ArrayList<>();

// 빈 트리인 경우 탐색할 필요가 없으므로 빈 리스트를 바로 return
if(root == null) return result;

// 탐색에 사용할 큐
Queue<TreeNode> q = new LinkedList<>();

 

큐를 이용한 탐색의 과정은 다음과 같다.

먼저 전달받은 트리의 root 노드를 큐에 넣은 상태로 탐색을 시작한다.

// root를 큐에 넣고 탐색 시작
q.offer(root);

 

큐의 사이즈를 구하고 그 사이즈만큼 반복하며 큐에서 노드를 꺼내어 리스트에 추가한다.
첫 번째 탐색의 경우 한 번, 즉 1레벨 노드의 탐색이 가능하다.
그리고 꺼낸 노드의 좌우 노드를 큐에 추가한다.

1레벨 노드의 탐색이 종료되고 나면 1레벨 노드들은 큐에서 모두 빠지고 2레벨의 노드만이 남게 된다.
큐의 사이즈를 다시 구하고 위의 과정을 반복하면 각 레벨별로 노드의 리스트를 구할 수 있게된다.

// 큐가 빌 때까지 반복
while(!q.isEmpty()){
    // 현재 큐의 사이즈만큼 반복 -> 같은 레벨

    // 현재 레벨의 노드들이 담길 리스트
    List<Integer> curLevel = new ArrayList<>();

    // 큐의 사이즈 -> 같은 레벨이 담겨있는 만큼
    int size = q.size();
    for(int i = 0; i < size; i++){
        // 큐에서 값을 꺼냄
        TreeNode curNode = q.poll();
        // 현재 레벨의 리스트에 노드 추가
        curLevel.add(curNode.val);
        // 현재 노드의 좌우 노드를 큐에 추가
        if(curNode.left != null) q.offer(curNode.left);
        if(curNode.right != null) q.offer(curNode.right);
    }

    // 현재 레벨 노드 리스트를 정답 리스트에 추가
    result.add(curLevel);
}

 

최종적으로 만들어진 리스트를 return 한다.

// 최종 결과값 반환
return result;

---

최종 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 반환할 결과값 리스트
        List<List<Integer>> result = new ArrayList<>();

        // 빈 트리인 경우 탐색할 필요가 없으므로 빈 리스트를 바로 return
        if(root == null) return result;

        // 탐색에 사용할 큐
        Queue<TreeNode> q = new LinkedList<>();

        // root를 큐에 넣고 탐색 시작
        q.offer(root);

        // 큐가 빌 때까지 반복
        while(!q.isEmpty()){
            // 현재 큐의 사이즈만큼 반복 -> 같은 레벨

            // 현재 레벨의 노드들이 담길 리스트
            List<Integer> curLevel = new ArrayList<>();

            // 큐의 사이즈 -> 같은 레벨이 담겨있는 만큼
            int size = q.size();
            for(int i = 0; i < size; i++){
                // 큐에서 값을 꺼냄
                TreeNode curNode = q.poll();
                // 현재 레벨의 리스트에 노드 추가
                curLevel.add(curNode.val);
                // 현재 노드의 좌우 노드를 큐에 추가
                if(curNode.left != null) q.offer(curNode.left);
                if(curNode.right != null) q.offer(curNode.right);
            }

            // 현재 레벨 노드 리스트를 정답 리스트에 추가
            result.add(curLevel);
        }

        // 최종 결과값 반환
        return result;
    }
}

---