Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

一.题目介绍

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+树得实现。另外题友们得解题思路是真的’脑洞大开’，十分的巧妙，目前自己只能使用笨方法，但是算法不是一蹴而就的，得持之以恒，加油！！！