public List<List<Integer>> solutionZigzag(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();

        if (root == null) {
            return list;
        }
        boolean zigzag = true;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Stack<TreeNode> subStack = new Stack<TreeNode>();
            ArrayList<Integer> subList = new ArrayList<Integer>();

            while (!stack.isEmpty()) {
                TreeNode t = stack.pop();
                subList.add(t.val);
                if (zigzag) {
                    if (t.left != null) {
                        subStack.push(t.left);
                    }
                    if (t.right != null) {
                        subStack.push(t.right);
                    }

                } else {
                    if (t.right != null) {
                        subStack.push(t.right);
                    }
                    if (t.left != null) {
                        subStack.push(t.left);
                    }
                }
            }
            stack.addAll(subStack);
            list.add(subList);
            zigzag = !zigzag;
        }
        return list;
    }