Binary Tree Level Order Traversal

🔗 문제 링크

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

🔍 문제 설명

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).

⚠️ 제한사항

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

---

🗝 풀이 (언어 : Java)

조금 난해한 문제였다. 큐를 사용할지가 애매했고, 큐가 텅빌때까지 반복해야 했지만 동시에 다음 자식 노드를 넣어주어야 했기에 어떻게 처리해야하는지 고민이었다. 답은 해당 시점의 큐의 size만큼 내부 반복문을 돌려서 해당 Level 만큼의 원소를 채워주면 된다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        // 트리 노드의 원소가 하나도 없는 경우 제외
        if (root != null)
            queue.offer(root);
        // 큐의 모든 원소를 리스트에 넣을 때까지 반복
        while (!queue.isEmpty()) {
            // 아래 반복문에서 i < queue.size로 하면 가변적이라 변수로 
            int size = queue.size();
            // 안쪽 채워줄 리스트 선언
            List<Integer> list = new ArrayList<>();
            // 현재 시점의 큐 사이즈만큼 반복하면 Level별 개수만큼 리스트에 넣는다
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                list.add(treeNode.val);
                // 만약 자식 트리 노드가 null이면 큐에 넣지 않는다
                if (treeNode.left != null)
                    queue.offer(treeNode.left);
                if (treeNode.right != null)
                    queue.offer(treeNode.right);
            }
            // 만든 리스트를 최종 리스트에 넣는다
            answer.add(list);
        }
        return answer;
    }
}