Accepted simple and straightforward Java solution


  • 0
    J

    The idea is just use two stack to store current layer and next layer, and determine how to store next layer by whether current layer is at odd or even position.

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            
            List<List<Integer>> res=new ArrayList<List<Integer>>();
            if(root==null)return res;
            Stack<TreeNode> cur=new Stack<TreeNode>();
            Stack<TreeNode> next=new Stack<TreeNode>();
            cur.push(root);
            int count=0;
            
            while(!cur.isEmpty()){
                List<Integer> temp=new ArrayList<Integer>();
                while(!cur.isEmpty()){
                    TreeNode now=cur.pop();
                    temp.add(now.val);
                    if(count%2==0){
                        if(now.left!=null)next.push(now.left);
                        if(now.right!=null)next.push(now.right);
                    }
                    else{
                        if(now.right!=null)next.push(now.right);
                        if(now.left!=null)next.push(now.left);
                    }
                }
                res.add(temp);
                count++;
                cur=next;
                next=new Stack<TreeNode>();
            }
            return res;
        }
    }

Log in to reply
 

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