Concise Java Solution; BFS; With Comments


  • 1
    V

    Time complexity: O(n), space complexity: O(n)

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null){
                return res;
            }
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            //Indicate the level
            int zig = 1;
            //Record size of current level
            int count = 0;
            TreeNode cur;
            while(queue.size()>0){
                List<Integer> temp = new ArrayList<Integer>();
                count = queue.size();
                
                for(int i = 0; i < count; i++){
                    cur = queue.remove();
                    if(zig % 2 == 0){
                        temp.add(0, cur.val);//Reversely add
                    }else{
                        temp.add(cur.val);
                    }
                    if(cur.left != null){
                        queue.add(cur.left);    
                    }
                    if(cur.right != null){
                        queue.add(cur.right);
                    }
                }
                
                res.add(temp);
                zig++;
            }
            return res;
        }
    }

  • 0
    W
    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            if (root == null) return ret;
            Deque<TreeNode> q = new ArrayDeque<TreeNode>();
            q.addLast(root);
            int dir = 1;
            while(!q.isEmpty()){
                int qsize = q.size();
                
                List<Integer> level = new ArrayList<Integer>();
                for (int i=0;i<qsize;++i){
                    TreeNode t = q.removeFirst();
                    if (t.left != null) q.addLast(t.left);
                    if (t.right != null) q.addLast(t.right);
                    if (dir == 1){
                        level.add(t.val);
                    } else {
                       level.add(0,t.val); 
                    }
                }
                dir = dir ^ 1;
                ret.add(level);
            }
            return ret;
        }
    }

Log in to reply
 

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