二叉树的锯齿形层序遍历

说在前面

🎈今天给大家带来的是算法练习,题目为"二叉树的锯齿形层序遍历"。

问题描述

给你二叉树的根节点 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

思路分析

这道题目也是树的遍历衍生出来的一道题目，所谓的锯齿形层序遍历其本质上还是层序遍历，只要知道层序遍历的写法，其实这道题目也是不难的，所以先让我们来回顾一下二叉树的层序遍历。

二叉树层序遍历

层序遍历就是以层为遍历顺序，先把第一层的节点遍历完再遍历第二层的节点，遍历顺序如下图所示：

二叉树的层序遍历主要是利用队列的先入先出思想进行解题，把每一层节点的子节点按顺序入队，那么出队的节点就是二叉树层序遍历的结果了。
关于层序遍历的题目我之前也有写过一篇博客，不了解的可以先到这里看看-> N 叉树的层序遍历

二叉树锯齿形遍历

锯齿形遍历也是层序遍历，其遍历顺序如下图：

由上图可以看出，我们只需要将层序遍历的某些层遍历结果翻转过来就可以了，如本题，我们只需要将层级为奇数的层遍历结果翻转过来保存到结果集里即可。

• 使用队列保存节点集
• 根据层级判断是否需要翻转
• 一层遍历完将本层结果翻入结果集合

具体代码如下：

AC代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    let queue = [{r:root,floor:0}];
    let nowFloor = 0;
    let res = [];
    let temp = [];
    while(queue.length){
        let q = queue.shift();
        if(!q.r) break;
        if(nowFloor != q.floor){
            res.push([...temp]);
            nowFloor = q.floor;
            temp = [];
        }
        q.floor % 2 == 0 ? temp.push(q.r.val) : temp.unshift(q.r.val);
        if(q.r.left) queue.push({r:q.r.left,floor: q.floor + 1});
        if(q.r.right) queue.push({r:q.r.right,floor: q.floor + 1});
    }
    if(temp.length) res.push([...temp]);
    return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。