LeetCode 102(Binary Tree Level Order Traversal, java)

0. 문제

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

Binary Tree Level Order Traversal - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)가 주어진다.

- 이진트리(root)를 깊이 단위로 탐색하며, 동일한 깊이에 있는 모든 노드를 하나의 배열로 묶는다.

- 이렇게 깊이 단위로 묶인 각 배열을 하나의 배열 안에 넣어 반환하는 것이 문제의 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 깊이 단위로 탐색을 진행하는 것이 이 문제의 핵심이다.

- 그러므로 깊이가 한 단계씩 증가할 때마다 해당 깊이에 존재하는 모든 노드를 확인해야 한다.

 

- 이 과정을 풀어내기 위해서 Queue 자료구조를 이용한다. 

- 일반적으로 이진트리를 탐색할 때에는 가장 좌측 노드부터 우측 노드로 탐색한다.

- 그러므로 탐색의 순서가 보장되어야 한다.

- 이와 같은 이유로 선입선출의 순서를 갖는 Queue 자료구조를 이용한다.  

 

b) 두 번째 접근

- 최초에 Queue 자료구조에는 루트 노드를 삽입하여 초기화한다.

- 반복문을 통해 Queue에 저장된 노드를 하나씩 뽑아내면서 해당 노드가 가진 자식 노드를 탐색한다.

- 이 방식은 동일한 깊이에 위치하는 노드의 자식 노드를 탐색하기 위함이다.

 

- 동일한 깊이를 가지는 부모 노드의 자식 노드 또한 모두 동일한 깊이를 갖는다.

- 그러므로 이 자식 노드를 모두 Queue에 저장한다.

- 이렇게 Queue에 저장된 자식 노드는 또 다른 자식 노드를 탐색하기 위해 사용된다.  

 

c) 세 번째 접근

- 반복문을 통해 Queue를 탐색하기 전에 Queue에 저장된 노드의 수를 알아야 한다.

- Queue를 탐색하면서 발견되는 각 노드의 자식 노드 또한 Queue에 저장되기 때문이다.

- 그러므로 각 깊이마다 몇 개의 노드가 있는지 알아야 정확한 탐색을 수행한다. 

 

- 즉, Queue를 한번 탐색할 때마다 깊이가 하나씩 증가하는 것이다. 

 

- 이 과정을 수행하기 위해서 다음과 같은 반복문이 필요하다.

    → Queue를 탐색하는 반복문 

    → 내용이 갱신된 Queue를 다시 탐색하도록 하는 반복문. 즉, 깊이를 갱신하는 역할의 반복문이다.

 

- 즉, 이중 반복문을 사용해야 한다. 

 

- 글로 이해하기에는 조금 힘들 수 있다.

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> result = new ArrayList<>();
        
        if(root == null) return result;
        
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        
        while(que.isEmpty() == false) {
            List<Integer> sameLevelList = new ArrayList<>();
            int size = que.size();
            
            for(int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                sameLevelList.add(node.val);
                
                if(node.left != null) {
                    que.add(node.left);
                }
                
                if(node.right != null) {
                    que.add(node.right);
                }
            }
            result.add(sameLevelList);
        }
        return result;
    }
}