My two stack Java solution


  • 0
    T
    public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Deque<TreeNode> lrstack = new LinkedList<>();
        Deque<TreeNode> rlstack = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        rlstack.push(root);
        while (true) {
            List<Integer> rlist = new ArrayList<>();
            while (!rlstack.isEmpty()) {
                TreeNode node = rlstack.pop();
                rlist.add(node.val);
                if (node.left != null)
                     lrstack.push(node.left);
                if (node.right != null)
                    lrstack.push(node.right);
            }
            if (rlist.size() != 0)
                result.add(rlist);
            
            List<Integer> llist = new ArrayList<>();
            while (!lrstack.isEmpty()) {
                TreeNode node = lrstack.pop();
                llist.add(node.val);
                if (node.right != null)
                    rlstack.push(node.right);
                if (node.left != null)
                    rlstack.push(node.left);
            }
            if (llist.size() != 0)
                result.add(llist);
            if (rlstack.isEmpty() && lrstack.isEmpty()) {
                break;
            }
        }
        return result;
        
    }
    

    }


Log in to reply
 

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