《剑指offer》 第32.3题 按之字形打印二叉树

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

本题是换行打印的升级版（在换行打印版本上进行更改），在换行打印时，将偶数列的添加顺序时进行翻转。如果牺牲一点效率，在翻转时采用头插法即可。
设置一个变量，区别奇数层和偶数层，然后进行不同的处理，在每一层的节点循环后，变量++，因此这个变量可以理解成树的深度。这道题和二叉树求深度紧密联系。

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > arrplus = new ArrayList<ArrayList<Integer> >();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(pRoot==null)
            return arrplus;
        queue.offer(pRoot);
        int depth=1;//第一层（同时也是深度）
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for (int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                if(depth%2==1){//奇数层
                    arr.add(node.val);//在尾部插入，正常的顺序
                }
                if(depth%2==0){//偶数层
                    arr.add(0,node.val);//头插法，效率低
                }
            }
            arrplus.add(arr);
            depth++;
        }
        return arrplus;
    }
}

2.一个优化的版本就是使用栈。利用栈来调整顺序。

import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > arrplus = new ArrayList<ArrayList<Integer> >();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Stack<Integer> stack = new Stack<>();
        if(pRoot==null)
            return arrplus;
        queue.offer(pRoot);
        int depth=1;//第一层（同时也是深度）
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for (int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                if(depth%2==1){//奇数层
                    arr.add(node.val);//在尾部插入，正常的顺序
                }
                if(depth%2==0){//偶数层
                    stack.push(node.val);//先放进栈
                }               
            }
            while(stack.size()!=0){ //在一层的都放进栈后，在倒给数组。
                arr.add(stack.pop());
            }
            arrplus.add(arr);
            depth++;
        }
        return arrplus;
    }
}

3.这里其实还可以不使用栈，在添加的时候，换一个添加方式，奇数层，先添加左节点，再添加右节点。偶数层，先添加右节点，再添加左边节点。写起来容易出错。有许多点需要注意。题解中，jav大佬给出的是这种版本。