1. 题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
2. 题目分析
- 首先该题类似于—【剑指offer】-把二叉树打印成多行-43/67
- 唯一不同的地方，在于左右输出，我们这里一般有3种方法来做
- 第一种，也是比较容易想到的一种，我们在储存List的时候，分成偶奇位，偶数的话，实施
Collections.reverse(list2); - 第二种，使用双向队列，双向队列的解释，奇数层的话，用
TreeNode node = deque.removeFirst();获取，将左子树右子树按照deque.addLast存储，偶数层的话，用TreeNode node = deque.removeLast();获取，将右子树和左子树按照deque.addFirst存储 - 第三种方法：利用两个栈来进行存储，将奇数层存储到stack1中，然后将stack1中的进行输出且将左子树和右子树存储到stack2中，将stack2中的进行输出且将右子树和左子树保存到stack1中
3. 题目代码
3.1 双向队列
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { Deque<TreeNode> deque = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if (root != null) deque.add(root); while (!deque.isEmpty()) { // 打印奇数层 List<Integer> tmp = new ArrayList<>(); for (int i = deque.size(); i > 0; i--) { // 从左向右打印 TreeNode node = deque.removeFirst(); tmp.add(node.val); // 先左后右加入下层节点 if (node.left != null) deque.addLast(node.left); if (node.right != null) deque.addLast(node.right); } res.add(tmp); if (deque.isEmpty()) break; // 若为空则提前跳出 tmp = new ArrayList<>(); for (int i = deque.size(); i > 0; i--) { TreeNode node = deque.removeLast(); tmp.add(node.val); if (node.right != null) deque.addFirst(node.right); if (node.left != null) deque.addFirst(node.left); } res.add(tmp); } return res; } }
3.2 两个栈
public List<List<Integer>> levelOrder3(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); if (root == null) { return list; } stack1.add(root); int num = 1; while (!stack1.isEmpty() || !stack2.isEmpty()) { if (num % 2 == 1) { // 奇数 List<Integer> list2 = new ArrayList<>(); while (!stack1.isEmpty()) { TreeNode treeNode = stack1.pop(); list2.add(treeNode.val); if (treeNode.left != null) { stack2.add(treeNode.left); } if (treeNode.right != null) { stack2.add(treeNode.right); } } list.add(list2); } else { // 偶数 List<Integer> list2 = new ArrayList<>(); while (!stack2.isEmpty()) { TreeNode treeNode = stack2.pop(); list2.add(treeNode.val); if (treeNode.right != null) { stack1.add(treeNode.right); } if (treeNode.left != null) { stack1.add(treeNode.left); } } list.add(list2); } num++; } return list; }
