[Java] leetcode 103. Binary Tree Zigzag Level Order Traversal

문제

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

Binary Tree Zigzag Level Order Traversal - LeetCode

알아야 할 개념

• BFS

풀이

풀이는 다음과 같다.  

1. 큐로 BFS를 구현한다. 
2. 해당 레벨 마다 노드를 큐에서 꺼내오고 꺼낸 값들을 리스트에 담는다.
3. 레벨이 홀수 일때만 리버스 적용한다.
4. 정답 배열에 리스트를 담는다. 
5. 정답을 리턴한다. 

코드

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> Q = new LinkedList<>();
        Q.offer(root);
        int level = 0;
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null)return ans;
        
        while(!Q.isEmpty()){
            int size = Q.size();
            List<Integer> l = new ArrayList<>();
            for(int i= 0 ;i < size;i ++){
                TreeNode node = Q.poll();
                l.add(node.val);
                if(node.left != null)Q.offer(node.left);
                if(node.right != null)Q.offer(node.right);
            }
            if(level % 2 != 0)Collections.reverse(l);
            ans.add(l);
            level++;
        }
        return ans;
    }
}