剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其层次遍历结果：
[ [3], [20,9], [15,7] ]
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
解题
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists = new ArrayList<>(); //如果等于null，就直接返回一个空的int[]数组 if(root==null) return lists; //利用队列先进先出的特性，保存每一个根节点 Queue<TreeNode> queue = new LinkedList<>(); //先把根入队 queue.offer(root); //定义一个数，用来判断奇数还是偶数 int pd = 1;//1:奇数，第1层，那么就从左到右。2：偶数，那么就从右到左。以此类推。每一层遍历完就pd++； Stack<Integer> stack = new Stack<>(); //队列不为空的时候，一直执行 while (!queue.isEmpty() || !stack.isEmpty()){ //存储每一层的数据 // List<Integer> list = new ArrayList<>(); LinkedList<Integer> list = new LinkedList<>(); //把每一层的数据给拿到 queue.size()的大小就是每一层节点的多少 for(int i=queue.size();i>0;i--){ //奇数 if(pd % 2 != 0){ //第一步：取出根元素,存储到list中（头插） list.addLast(queue.peek().val); }else{ //第一步：取出根元素,存储到list中（尾插） list.addFirst(queue.peek().val); } //第二步：弹出队列中的根元素 TreeNode pollRoot = queue.poll(); //第三步：分别把根的左子树和右子树入队 if(pollRoot.left!=null) queue.offer(pollRoot.left); if(pollRoot.right!=null) queue.offer(pollRoot.right); } lists.add(list); //层数+1 pd++; } // 将lists返回 return lists; } }
