Java Queue Solution with O(n)


  • 0
    J
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null)
                return res;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode curNode;
            int flag = 1;   //1:L-->R  0:R-->L
            while(!queue.isEmpty()){
                List<Integer> list = new LinkedList<>();
                int size = queue.size();
                for(int i = 0; i < size; ++i){
                    curNode = queue.poll();
                    if(curNode.left != null)    queue.offer(curNode.left);
                    if(curNode.right != null)   queue.offer(curNode.right);
                    if(flag == 1){
                        list.add(curNode.val);
                    }else{
                        list.add(0,curNode.val);
                    }
                }
                flag = (flag == 1) ? 0 : 1;
                res.add(list);
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.