问题描述

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

思路

可以用一个栈。照样层序遍历，只不过在倒着走的层用一个栈保存数字，遍历完了这层再吐出来。

方法一

class Solution {public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {ArrayList<ArrayList<Integer>> res = new ArrayList<>();if(pRoot == null) return res;boolean isRight = true; // 表示方向Queue<TreeNode> queue = new LinkedList<>();queue.add(pRoot);while(!queue.isEmpty()){Queue<TreeNode> next = new LinkedList<>();ArrayList<Integer> tmp = new ArrayList<>();Stack<Integer> stack = new Stack<>(); // 倒着来, 当然用栈while(!queue.isEmpty()){if(!isRight){stack.add(queue.peek().val);}else{tmp.add(queue.peek().val);}if(queue.peek() != null && queue.peek().left != null) next.add(queue.peek().left);if(queue.peek() != null && queue.peek().right != null) next.add(queue.peek().right);queue.poll();}while(!stack.isEmpty()) tmp.add(stack.pop());res.add(tmp);isRight = !isRight;queue = next;}return res;}
}