按之字形顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
时间限制: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表示从右到左)
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; } }