LeetCode 102. Binary Tree Level Order Traversal 자바 문제 풀이

문제

Binary Tree Level Order Traversal - LeetCode

문제 해결 방법

• level order라는것은 level 순서대로 출력하라는 뜻이며, BFS와 같습니다.
• BFS는 DFS와 달리 큐를 사용하며, 문제와 같은 경우 재귀함수보단 반복문을 사용하는 편이 더 알맞습니다.
• 즉, 이 문제는 BFS를 정확히 이해하고 구현할수 있느냐고 묻는 문제 입니다.

https://github.com/eunhanlee/LeetCode_102_BinaryTreeLevelOrderTraversal_Solution.git

시간복잡도: O(n), 공간복잡도: O(m:트리최대 넓이)

public class Solution {
    
    /**
     * 주어진 이진 트리에 대해 레벨 순서 순회를 수행하고 각 레벨의 노드 값을 포함한 리스트의 리스트를 반환합니다.
     *
     * @param root 이진 트리의 루트 노드
     * @return 각 레벨의 노드 값을 포함한 리스트의 리스트
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>(); // 결과를 저장할 리스트 생성

        if (root == null)
            return result; // 빈 트리인 경우 빈 결과 반환

        Queue<TreeNode> queue = new LinkedList<>(); // BFS를 위한 큐 생성
        queue.add(root); // 루트 노드를 큐에 추가

        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>(); // 현재 레벨의 노드 값을 저장할 리스트 생성
            int size = queue.size(); // 현재 레벨의 노드 개수

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll(); // 큐에서 노드를 꺼내옴
                level.add(node.val); // 노드 값을 현재 레벨 리스트에 추가

                if (node.left != null)
                    queue.add(node.left); // 왼쪽 자식 노드를 큐에 추가
                if (node.right != null)
                    queue.add(node.right); // 오른쪽 자식 노드를 큐에 추가
            }

            result.add(level); // 현재 레벨 리스트를 결과 리스트에 추가
        }

        return result; // 결과 리스트 반환
    }
}