描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

输出

[[1],[3,2],[4,5]]

---

栈解法

用两个栈来存奇数层和偶数层的节点，如果当前为奇数层则先入栈左孩子再入栈右孩子，如果为偶数层则先入栈右孩子再入栈左孩子

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class Solution {public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {ArrayList<ArrayList<Integer>> res = new ArrayList<>();if (pRoot == null)return res;boolean toright = true; // 向右输出Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.add(pRoot);while (!stack1.isEmpty() || !stack2.isEmpty()) {ArrayList<Integer> tmp = new ArrayList<>();if (toright) {// 向右输出 奇数层while (!stack1.isEmpty()) {TreeNode top = stack1.pop();tmp.add(top.val);if (top.left != null)stack2.add(top.left);if (top.right != null)stack2.add(top.right);}toright = false;} else {// 向右输出 偶数层while (!stack2.isEmpty()) {TreeNode top = stack2.pop();tmp.add(top.val);if (top.right != null)stack1.add(top.right);if (top.left != null)stack1.add(top.left);}toright = true;}res.add(tmp);}return res;}public static void main(String[] args) {TreeNode r = new TreeNode(8);r.left = new TreeNode(6);r.right = new TreeNode(10);r.left.left = new TreeNode(5);r.left.right = new TreeNode(7);r.right.left = new TreeNode(9);r.right.right = new TreeNode(11);System.out.println(new Solution().Print(r));}
}