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

这是一道将层次遍历和队列或者说是栈深度结合的好题

值得练手

import java.util.ArrayList;
import java.util.LinkedList;
/*
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 pRoot) {
        //申请一个树结点型的链表队列
        LinkedList<TreeNode> q = new LinkedList<>();
        //存储结果
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        boolean rev = true;

        q.add(pRoot);
        while(!q.isEmpty()){
            int size = q.size();//获取每一层的节点数，第一层一个
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0; i<size; i++){
                TreeNode node = q.poll();
                if(node == null){
                    continue;
                }
                if(rev){
                    list.add(node.val);
                }else{
                    list.add(0, node.val);
                }
                q.offer(node.left);
                q.offer(node.right);
            }
            if(list.size()!=0){
                res.add(list);
            }
            rev=!rev;
        }           
        return res;
    }   
}