Java solution with two stack


  • 0
    I
    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            if(root == null) return list;
            boolean zig = false;
            Stack<TreeNode> stack1 = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            stack1.push(root);
            while(!stack1.empty() || !stack2.empty()) {
                List<Integer> list1 = new ArrayList<>();
                while(!stack1.empty()) {
                    TreeNode node = stack1.pop();
                    list1.add(node.val);
                    if(node.left != null) stack2.push(node.left); //push left first
                    if(node.right != null) stack2.push(node.right);
                }
                if(list1.size() != 0) list.add(list1);
                List<Integer> list2 = new ArrayList<>();
                while(!stack2.empty()) {
                    TreeNode node = stack2.pop();
                    list2.add(node.val);
                    if(node.right != null) stack1.push(node.right); //push right first
                    if(node.left != null) stack1.push(node.left); 
                    
                }
                if(list2.size() != 0) list.add(list2);
                
            }
            return list;
        }
    }
    

Log in to reply
 

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