题目描述

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

时间限制：1秒 空间限制：32768K

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/

解题思路

1、使用队列层次遍历二叉树，同时使用flag标记当前层（true表示从左到右，false表示从右到左）

注意：本解法中tmp.add(0,e.val)比较耗时

import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> array=new ArrayList<>();
        if(pRoot==null) return array;
        LinkedList<TreeNode> queue=new LinkedList<>();
        ArrayList<Integer> tmp;
        queue.offer(pRoot);
        boolean flag=true;
        while(!queue.isEmpty()){
            int size=queue.size();
            tmp=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode e=queue.poll();
                if(flag) tmp.add(e.val);
                else tmp.add(0,e.val);
                if(e.left!=null) queue.offer(e.left);
                if(e.right!=null) queue.offer(e.right);
            }
            if(flag) flag=false;
            else flag=true;
            array.add(tmp);
        }
        return array;
    }
}