[Leetcode] 102. Binary Tree Level Order Traversal

문제 정의

root 가 주어졌을 때 레벨 순서대로 순회하며 각 노드의 값을 반환하라.

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

Binary Tree Level Order Traversal - LeetCode

 

풀이

어제 문제 마저 못풀고 오늘 풀이 쓰기가 살짝 찝찝하지만.. 쉬운 문제라서 먼저 풀었다.

이틀 전 풀었던 문제에서는 각 레벨의 가장 오른쪽 노드값을 차례대로 출력하면 되었는데 오늘 문제는 각 레벨별로 노드의 값을 하나의 List씩 만들어서 List<List<Integer> 를 반환하는 문제이다.

Queue에 자식노드를 추가하면서 레벨 노드를 탐색할 수 있다. 자식 노드를 추가하기 전의 큐의 size는 해당하는 depth에 존재하는 노드개수이므로, 그 size만큼 반복문을 돌면서 노드의 값을 List로 만들어준다. 

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            Queue<TreeNode> nodeQueue = new LinkedList<>();

            if (root == null) {
                return result;
            }
            nodeQueue.add(root);

            TreeNode curr;
            while(!nodeQueue.isEmpty()) {
                int size = nodeQueue.size();

                List<Integer> nodeList = new ArrayList<>();
                for (int i=0; i<size; i++) {
                    curr = nodeQueue.remove();

                    nodeList.add(curr.val);
                    if (curr.left != null) {
                        nodeQueue.add(curr.left);
                    }
                    if (curr.right != null) {
                        nodeQueue.add(curr.right);
                    }
                }
                result.add(nodeList);
            }
            return result;

        }
    }

쉬운 문제지만 한번에 풀면 기분 좋아^0^