Share my Java AC Non-recursion code


  • 0
    X
    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            if(root==null) return ret;
            Queue<TreeNode> q=new LinkedList<TreeNode>();
    
            q.offer(root);
            boolean level=false;
            
            while(!q.isEmpty()){
                int cnt=q.size();
                LinkedList<Integer> tmp=new LinkedList<Integer>();
                for(int i=0;i<cnt;i++){
                    if(level){
                        TreeNode head=q.poll();
                        tmp.addFirst(head.val);
                        if(head.left!=null)
                            q.offer(head.left);
                        if(head.right!=null) 
                            q.offer(head.right);
                    }else{
                        TreeNode head=q.poll();
                        tmp.add(head.val);
                        if(head.left!=null)
                            q.offer(head.left);
                        if(head.right!=null)
                            q.offer(head.right);
                    }        
                }
                ret.add(tmp);
                if(level){
                    level=false;
                }else{
                    level=true;
                }
            }
            return ret;     
        }
    }

Log in to reply
 

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