剑指offer系列之五十四：按之字形顺序打印二叉树

题目描述

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

此题明显是层序遍历的思路。由于需要按照之字形打印每一层，相当于在打印每一行之前需要判断上一行打印的顺序。比如，如果上一行打印的顺序使从左到右，那么下一行的打印顺序应该是从右到左。实现的这点可以采用奇数行从左到右打印，偶数行从右到左进行打印。还可直接设置 一个布尔变量，每打印一行就改变一次该变量的值。其他的就是层序遍历的思路了。下面是我实现的代码（已被牛客AC）：

package com.rhwayfun.offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class PrintBiTree {

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

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

        }

    }

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null) return resultList;
        //创建一个队列保存遍历的顺序
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(pRoot);
        //创建每一行遍历的结果
        ArrayList<Integer> result = new ArrayList<Integer>();
        boolean isLeftToRight = true;
        int begin = 0,end = 1;
        while(!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            result.add(curNode.val);
            begin++;
            if(curNode.left != null) queue.add(curNode.left);
            if(curNode.right != null) queue.add(curNode.right);
            //判断一行的所有元素是否都添加到result中
            if(begin == end){
                //判断当前行按照怎样的顺序打印
                if(!isLeftToRight){
                    resultList.add(reverse(result));
                }else{
                    resultList.add(result);
                }
                //下一行需要改变方向
                isLeftToRight = !isLeftToRight;
                end = queue.size();
                begin = 0;
                //一行打印完毕之后，需要创建的result集合保存下一行遍历的元素
                result = new ArrayList<Integer>();
            }
        }
        return resultList;
    }

    private ArrayList<Integer> reverse(ArrayList<Integer> result) {
        int size = result.size();
        ArrayList<Integer> reverseResult = new ArrayList<Integer>();
        for(int i = size - 1; i >= 0; i--){
            reverseResult.add(result.get(i));
        }
        return reverseResult;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(10);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(9);
        TreeNode node6 = new TreeNode(11);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;

        ArrayList<ArrayList<Integer>> list = new PrintBiTree().Print(root);
        for (ArrayList<Integer> arrayList : list) {
            System.out.println(arrayList);
        }
    }
}