public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        Stack<TreeNode> prev = new Stack<TreeNode>();
        Stack<TreeNode> curr = new Stack<TreeNode>();
        prev.add(root);
        boolean reversed = true;
        while (!prev.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            while (!prev.isEmpty()) {
                TreeNode p = prev.pop();
                level.add(p.val);
                if (reversed) {
                    if (p.left != null) curr.push(p.left);
                    if (p.right != null) curr.push(p.right);
                } else {
                    if (p.right != null) curr.push(p.right);
                    if (p.left != null) curr.push(p.left);
                }
            }
            // No need to null check level since level should always be non empty.
            result.add(level);
            // No need to create new stack for curr since prev is already empty, so just reuse prev.
            Stack<TreeNode> tmp = prev;
            prev = curr;
            curr = tmp;
            reversed = !reversed;
        }
        return result;
    }