题解 | #按之字形顺序打印二叉树#

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        //保存总遍历结果
        ArrayList<ArrayList<Integer>>lists = new ArrayList<>();
        if(root==null){
            return lists;   
        }
	  //利用先进先出特性来遍历每层元素
        Queue<TreeNode> queue = new ArrayDeque<>();
	  //用来反转偶数行的元素
        Stack<Integer> stack = new Stack<>();
	  //入队根节点
        queue.add(root);
	  //用来标记哪层进行反转
        int num = 1;
        while (!queue.isEmpty()) {
            //每次清空栈
            stack.clear();
            //将每层元素添加到row集合
            ArrayList<Integer> row = new ArrayList<>();
            int size = queue.size();
		  //遍历每层
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                row.add(cur.val);
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            //偶数层逆转
            if (num % 2 == 0) {
			  //将偶数层元素入栈
                int rowSize = row.size();
                for (int i = 0; i < rowSize; i++) {
                    stack.add(row.get(i));
                }
			  //清空偶数层
                row.clear();
			  //出栈并入集合
                while (!stack.isEmpty()) {
                    row.add(stack.pop());
                }
            }
            num++;
            lists.add(row);
        }


        return lists;
    }

}