一.题目介绍
1.题目来源
链接：LeetCode
2.题目
给你二叉树的根节点root ，返回其节点值的锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1： 输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2： 输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目在范围 [0, 2000] 内 -100 <= Node.val <= 100
二.具体实现
1.实现思路
使用两个栈来实现。栈的特点，是先进后出，栈1从右至左存储，栈2从左至右存储，然后由根节点开始入栈，再由测试元素按栈1再栈2的方式入栈即可实现。
2.实现代码
1)自己的实现方式
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); //有一些小伙伴可能会忽略这一步，刷多了就知道了 if (root == null) { return list; } //栈1来存储右节点到左节点的顺序 Stack<TreeNode> stack1 = new Stack<>(); //栈2来存储从左节点到右节点的顺序 Stack<TreeNode> stack2 = new Stack<>(); //根节点入栈 stack1.push(root); while (!stack1.isEmpty() || !stack2.isEmpty()) { // 存储这一个层的数据 List<Integer> subList = new ArrayList<>(); TreeNode cur = null; if (!stack1.isEmpty()) { while (!stack1.isEmpty()) { cur = stack1.pop(); subList.add(cur.val); if (cur.left != null) { stack2.push(cur.left); } if (cur.right != null) { stack2.push(cur.right); } } list.add(subList); } else{ while (!stack2.isEmpty()){ cur = stack2.pop(); subList.add(cur.val); if (cur.right != null) { stack1.push(cur.right); } if (cur.left != null) { stack1.push(cur.left); } } list.add(subList); } } return list; } } 复制代码
2)题友的实现方式
不使用栈，而是遍历二叉树，并用双向链表添加数据，偶数层正着加，奇数层倒着加即可实现，只能说十分的巧妙了，赞！
3.运行结果
三.题后思考
关于二叉树的题目其实是我的弱项，虽然二叉树不是很难理解，但是从学校开始接触二叉树开始就对它不是很感冒，所以很多时候都避开它，但是再难咬的骨头也的得啃，二叉树运用在很多程序的底层实现里，比如MySQL的索引实现就是B+树，我们懂得使用索引的同时也得知道，索引为什么这么快，而其快的原因就是底层里B+树得实现。另外题友们得解题思路是真的'脑洞大开'，十分的巧妙，目前自己只能使用笨方法，但是算法不是一蹴而就的，得持之以恒，加油！！！
