剑指offer：按之字形顺序打印二叉树

题意描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路

一、思路一

1. 使用两个栈，一个栈保存奇数层，一个栈保存偶数层。
2. 遍历奇数层时，奇数栈中的元素添加入list集合，将子节点入偶数栈；遍历偶数层时，偶数栈中的元素添加入集合，将子节点入奇数栈
3. 入偶数栈时，左孩子先入栈，右孩子后入栈；入奇数栈时，右孩子先入栈，左孩子后入栈

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null) return res;
        Stack<TreeNode> s1 = new Stack<>();	//奇数栈
        Stack<TreeNode> s2 = new Stack<>();	//偶数栈
        s1.push(pRoot);	//根节点入栈
        while(!s1.empty() || !s2.empty()){
            if(!s1.empty()){	//奇数层
                ArrayList<Integer> list = new ArrayList<>();
                while(!s1.empty()){
                    TreeNode node = s1.pop();
                    if(node != null){
                        //奇数栈元素添加入list
                        list.add(node.val);	
                        //偶数层入栈，先左后右
                        s2.push(node.left);	
                        s2.push(node.right);
                    }
                }
                if(!list.isEmpty()){
                    res.add(list);
                }
            }else{	//偶数层
                ArrayList<Integer> list = new ArrayList<>();
                while(!s2.empty()){	
                    TreeNode node = s2.pop();
                    if(node != null){
                        //偶数层添加入list集合
                        list.add(node.val);
                        //奇数层入栈，先右后左
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if(!list.isEmpty()){
                    res.add(list);
                }
            }
        }
        return res;
    }
}	

二、思路二

利用BFS算法的思想

    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if(pRoot == null) return res;
            travel(res,0,pRoot);
            return res;
        }
        //lev记录当前遍历的层数
        private void travel(ArrayList<ArrayList<Integer>> res, int lev,TreeNode root){
            if(root == null) return;
            //遍历新层之前，对res进行扩容
            if(res.size() <= lev){
                res.add(new ArrayList<Integer>());
            }
            if(lev % 2 == 0){	//奇数层
                res.get(lev).add(root.val);	//从尾部添加，正序
            }else{	//偶数层
                res.get(lev).add(0,root.val);//从头部添加，倒序
            }
            travel(res,lev+1,root.left);	//左子节点递归
            travel(res,lev+1,root.right);	//右子节点递归
        }

    }

剑指offer：按之字形顺序打印二叉树

原文：https://www.cnblogs.com/le-le/p/12860125.html