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

两种方式的层序遍历完成

第一种:使用两个变量curLevelLast和nextLevelLast来知晓层的转变，每次在当前层结束之后就进行答案收集

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    Queue<TreeNode> queue = new LinkedList<>();
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    queue.add(pRoot);
    TreeNode curLevelLast = pRoot,nextLevelLast = null;
    //每次在上一层就把下一层都给解决了，
    int level = 1;
    ArrayList<Integer> levelRes = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    while(!queue.isEmpty()&&queue.peek()!=null){
        TreeNode cur = queue.poll();
        boolean isOdd = (level&1)!=0;
        if(isOdd){
            //奇数层
            levelRes.add(cur.val);
        }else{
            //偶数
            stack.push(cur.val);
        }
        if(cur.left!=null){
            queue.add(cur.left);
            nextLevelLast = cur.left;
        }
        if(cur.right!=null){
            queue.add(cur.right);
            nextLevelLast = cur.right;
        }
        if(cur==curLevelLast){
            //结算当前层
            if(!isOdd){
                while(!stack.isEmpty()){
                    levelRes.add(stack.pop());
                }
            }
            res.add(levelRes);
            levelRes = new ArrayList<>();
            curLevelLast = nextLevelLast;
            level++;
        }
    }
    return res;
}

这种感觉是比较复杂的

第二种：每次进入循环的时候就解决一层，这样是比较简单的

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer> > res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(pRoot);
    boolean isOdd = true;
    ArrayList<Integer> levelRes = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    while(!queue.isEmpty()&&queue.peek()!=null){
        int levelSize = queue.size();
        //把一层都给收集了
        for(int i = 0;i<levelSize;i++){
            TreeNode node = queue.poll();
            if(isOdd){
                levelRes.add(node.val);
            }else{
                stack.push(node.val);
            }
            if(node.left!=null) 
                queue.add(node.left);
            if(node.right!=null) 
                queue.add(node.right);
        }
        if(!isOdd){
            while(!stack.isEmpty()){
                levelRes.add(stack.pop());
            }
        }
        res.add(levelRes);
        levelRes = new ArrayList<>();
        isOdd = !isOdd;
    }
    return res;
}