[LeetCode] 102. Binary Tree Level Order Traversal

문제

트리 문제이다.

binary tree의 root 노드가 주어질 때, level(층)을 순서대로 각 노드의 value들을 2차원 배열로 저장하여 리턴하는 문제이다.

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

Binary Tree Level Order Traversal - LeetCode

풀이

각 층에 있는 노드의 value들을 확인하는 문제이다. 확인하는 순서는 오른쪽->왼쪽 순서이다.

Queue를 활용하여 너비우선탐색을 한다.

위 그림을 보면, 각 층에는 노드들이 있다.

 

먼저, 큐에 root 노드를 삽입한다.

큐의 크기를 size라고 할 때, size 만큼 다음을 반복한다.

- 큐에서 노드를 하나 꺼내어, 그 노드의 값을 리스트에 저장한다.

- 꺼낸 노드의 left/right 노드가 null이 아니면, 그 노드를 큐에 삽입한다.

 

이것을 반복하면, while문을 한 번 끝날 때마다, 각 층의 노드를 모두 확인한 것이 되고

큐에 있는 노드는 다음 층의 노드만 남아있게 된다.

 

(위 그림 예시)

루트노드를 하나 큐에 삽입한다.

1층) size=1이므로 큐에서 노드 1개를 꺼내 확인하고, 각 child들을 담는다. (child 2개)

2층) size=2이므로 큐에서 노드 2개를 꺼내 확인하고, 각 child들을 담는다. (child 2개)

3층) size=2이므로 큐에서 노드 2개를 꺼내 확인하고, 각 child들을 담는다. (child 0개)

-> 다음 층이 없기 때문에 (child가 없기 때문에!)  지금까지 저장한 value들을 담아 리턴한다.

코드

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

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) { // 노드를 모두 확인
            int size = q.size(); // 현재 큐에 들어있는 노드 수 (한 층의 노드 수)
            ArrayList<Integer> values = new ArrayList<>();
            while (size > 0) {
                TreeNode node = q.poll();
                values.add(node.val);
                if (node.left != null) // child node (left)
                    q.add(node.left);
                if (node.right != null) // child noe (right)
                    q.add(node.right);
                size--;
            }
            answer.add(values);
        }

        return answer;
    }