Leetcode 103. 二叉树的锯齿形层序遍历 （Java+Python3实现 超详细注释！）

Leetcode 103. 二叉树的锯齿形层序遍历

之前写过Python版本的层序遍历，这道题只是加了一个锯齿形遍历，基本思路是一致的，Java和Python都实现了一遍，Python没加注释，详细的注释可以看之前写的那道题。Java版加了详细的注释，方便日后复习，也希望能帮到其他小伙伴，如有错误，欢迎指正！

Java实现：

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 初始化一个二维的链表，存储最终返回的结果
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        // 判空
        if (root == null) return res;
        // 初始化一个链表，用来存储该二叉树每层的节点
        List<TreeNode> que = new LinkedList<TreeNode>();
        // 初始插入一个根节点
        que.add(root);
        // 由于需要锯齿形层序遍历，所以我们定义一个布尔值flag，用来判断每层遍历结果的顺序
        boolean flag = true;
        // 只要que中还有节点，说明二叉树没遍历完，就一直遍历
        while (!que.isEmpty()){
            // 初始化一个链表，用来存储下一层的节点
            List<TreeNode> tmp = new LinkedList<TreeNode>();
            // 初始化一个链表，用来存储当前层的节点值
            List<Integer> tmp_val = new LinkedList<Integer>();
            // 遍历当前层的所有节点
            for (TreeNode q : que){
                // 锯齿遍历，先从左往右，再从右往左，因此第一次是尾插，第二次头插，第三次尾插，以此类推...
                // 因此我们定义flag为true就尾插，false就头插
                if (flag){
                    tmp_val.add(q.val);
                }else{
                    tmp_val.add(0,q.val);
                }
                // 我们每遍历一个节点，就把该节点的子节点放入下一层要遍历的链表中
                if (q.left != null){
                    tmp.add(q.left);
                }
                if (q.right != null){
                    tmp.add(q.right);
                }
            }
            // 把当前层的节点值链表放入res中，这里就体现出前面定义链表时都用List接收的优势了，统一类型，避免不必要的强转
            // 这也是为什么我tmp_val的类型用的是链表，而不是deque，
            // deque可以直接永offerLast()和offerFirst(),非常方便，但是在这里就需要将deque强转成List
            res.add(tmp_val);
            // 重新将tmp作为下一次遍历的que，我个人喜欢直接替换，而不是增删que
            que = tmp;
            // 每次遍历完一层就反转flag
            flag = !flag;
        }
        return res;
    }
}

Python3实现：

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        # 方法1：翻转结果（代码少，好理解，但是应该略微慢一些）
        if not root:
            return []
        que = [root]
        result = []
        flag = True
        while que:
            tmp = []
            tmp_val = []
            flag = not flag
            for node in que:
                tmp_val.append(node.val)
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            if flag:
                tmp_val.reverse()
            result.append(tmp_val)
            que = tmp
        return result

        # 方法2：头插+尾插（这种速度应该略微会快一点）
        if not root:
            return []
        que = [root]
        result = []
        flag = True
        while que:
            tmp = []
            tmp_val = []
            flag = not flag
            for node in que:
                if not flag:
                    tmp_val.append(node.val)
                else:
                    tmp_val.insert(0,node.val)
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            result.append(tmp_val)
            que = tmp
        return result