[LeetCode] Binary Tree Level Order Traversal

 

leetcode.com/explore/featured/card/top-interview-questions-easy/94/trees/628

Explore - LeetCode

레벨 순회하기 (큐를 이용!)

 

LinkedList를 parent 노드와 child 노드로 나누어서 while 문에서 해결하려고 했는데 잘 안됐다.

못풀어서 답을 본 문제

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

1. null 인경우 리턴을 바로 해주고 아니라면 큐를 만들기

1. 큐에 root 노드를 담는다.
2. 큐가 비어있지 않은 동안 반복
   2-1. 큐의 사이즈를 얻는다.
   2-2. 노드 목록을 저장하기 위한 List 변수 생성 (subList)
   2-3. size가 0보다 큰 동안, 즉 큐에 노드가 있는 동안 반복
     2-3-1. 제일 처음 삽입한 노드를 하나 꺼내서 List에 값을 담는다.
     2-3-2. 해당 노드의 자식 노드가 있으면 큐에 담는다. (왼쪽/오른쪽 자식 노드 모두)
     2-3-3. size --;
3. 작업이 끝나면 result 변수에 subList를 담는다.
4. result 변수 리턴

 

Binary Tree Level Order Traversal