Binary Tree Level Order Traversal (Queue)

LeetCode의 Binary Tree 튜토리얼의 첫 번째 섹션의 네 번째 문제인 Binary Tree Level Order Traversal다.

이전 Binary Tree Inorder Traversal (Stack) 포스트에서 간단하게 다루었던 Level-order 방식으로 탐색하는 문제다. 이는 같은 높이에 있는 모든 노드를 한 번에 탐색하는 것이기 때문에 약간 BFS와 유사하다고 볼 수 있다.

위처럼 여러 계층의 노드가 있을 때 첫 번째 계층에 있는 노드는 노드 1밖에 없기 때문에 이를 탐색하고 두 번째 계층에 있는 노드는 노드 2, 노드 3이 있기 때문에 이를 둘 다 탐색한다. 그리고 세 번째 계층에 있는 노드는 노드 4, 노드 5가 있기 때문에 역시 이를 둘 다 탐색한다. 이렇게 한 계층, 높이, 레벨씩 탐색하려면 어떻게 해야 할까?

 

큐를 활용한다면 현재 큐에 있는 모든 노드에 대하여 자식 노드를 구해서 큐에 삽입하는 방식으로 구현할 수 있다. 이 경우 새로 추가된 자식 노드가 현재 탐색 중인 노드와 헷갈리지 않도록 현재 큐에 삽입된 노드의 개수, 즉 현재 탐색 중인 노드의 개수를 구해서 그만큼만 큐에서 제거하여 탐색하도록 구현해야 할 것이다.

import java.util.LinkedList;


class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new LinkedList<>();
        
        LinkedList<List<Integer>> result = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> initResult = new LinkedList<>();
        
        initResult.add(root.val);
        result.add(initResult);
        
        queue.add(root);
        
        while(!queue.isEmpty()){
            LinkedList<Integer> subResult = new LinkedList<>();
            
            int limit = queue.size();
            
            while(limit-- > 0){
                TreeNode node = queue.pop();
                
                if(node.left != null){
                    queue.add(node.left);
                    subResult.add(node.left.val);
                }
                if(node.right != null){
                    queue.add(node.right);
                    subResult.add(node.right.val);
                }
            }
            
            if(subResult.size() > 0) result.add(subResult);
            
        }
        
        return result;
    }
}

이전 Post-order의 늪에 빠졌던 것에 비하면 매우 빠르게 풀 수 있었다. 예전에 교수님에게 들은 얘기로는 이런 Level-order 방식의 탐색이 디렉터리 구조에서 유용하다고 들었던 것 같다. 현재 폴더에 있는 파일들을 전부 탐색하고 폴더의 경우 큐에 삽입해서 다시 Level-order 탐색하여 디렉터리의 전체 구조를 파악한다던지 뭐 그런 것이다.