专栏首页前端小书童【一天一大 lee】二叉树的锯齿形层序遍历 (难度:中等) - Day20201222

【一天一大 lee】二叉树的锯齿形层序遍历 (难度:中等) - Day20201222

20201222

题目:

给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下:

[
  [3],
  [20,9],
  [15,7]
]

抛砖引玉

关于二叉树的按层遍历之前已经做过类似的题目:

二叉树的层序遍历二叉树的层次遍历 II

广度优先搜索(BFS)按层遍历模板:

let _result = [],
    queue = []
if (root == null) return []
queue.push(root)
while (queue.length) {
    let len = queue.length,
        levelNodes = []
    for (let i = 0; i < len; i++) {
        let node = queue.shift()
        levelNodes.push(node.val)
        if (node.left) {
            queue.push(node.left)
        }
        if (node.right) {
            queue.push(node.right)
        }
    }
    _result.push(levelNodes)
}
return _result

取二叉树节点放到队列中,每次遍历队列(清空队列)将队列中节点取出,节点值存放到新数组中, 再将取出的节点的子节点放入队列中。

抛砖引玉

本题中要求遍历顺序,每次顺序与上一次想法,则可以通过已经遍历的层数的奇偶来切换该层元素的排列顺序

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    let _result = [],
        queue = []
    if (root == null) return []
    queue.push(root)
    while (queue.length) {
        let len = queue.length,
            levelNodes = []
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            levelNodes.push(node.val)
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 根据已遍历的层数切换元素的排列顺序
        _result.length % 2
            ? _result.push(levelNodes.reverse())
            : _result.push(levelNodes)
    }
    return _result
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一天一大 lee(二叉树的中序遍历)难度:中等-Day20200914

    递归方法采用了深度优先遍历的形式,一般可以采用深度优先遍历就可以采用广度优先遍历。

    前端小书童
  • 【一天一大 lee】二叉树的后序遍历 (难度:中等) - Day20200929

    前端小书童
  • 【一天一大 lee】二叉树的前序遍历 (难度:中等) - Day20201027

    前端小书童
  • 每天一道leetcode-103二叉树的锯齿形层次遍历

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426

    乔戈里
  • leetcode 每日一题:103.二叉树的锯齿形层序遍历

    leetcode 每日一题:103.二叉树的锯齿形层序遍历:https://leetcode-cn.com/problems/binary-tree-zigza...

    用户7685359
  • 2021-10-06:二叉树的锯齿形层序遍历。给定一个二叉树,返

    2021-10-06:二叉树的锯齿形层序遍历。给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进...

    福大大架构师每日一题
  • 一天一大 lee(二叉树的层次遍历 II)难度:简单-Day20200906

    给定一个二叉树,返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

    前端小书童
  • 【一天一大 lee】从中序与后序遍历序列构造二叉树 (难度:中等)-Day20200925

    因为后续遍历是先遍历左子树再遍历右子树最后遍历根节点, 那么右子树的索引一定大于左子树的索引,当不满足是说明节点遍历完成,终止递归

    前端小书童
  • Leetcode No.103 二叉树的锯齿形层序遍历

    给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    week
  • 【leetcode刷题】T116-二叉树的锯齿形层次遍历

    https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

    木又AI帮
  • LeetCode 103. 二叉树的锯齿形层次遍历

    给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    TrueDei
  • ​LeetCode刷题实战103:二叉树的锯齿形层次遍历

    https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

    程序IT圈
  • 初识广度优先搜索与解题套路

    先来看看其中比较简单的数据结构 - 链表,它和数组类似,也是一个线性的结构,简单来说就是一条路径,你从头开始遍历,最终会将链表上面的节点都访问到,到达终点。

    五分钟学算法
  • 图解LeetCode第 103 号问题:二叉树的锯齿形层次遍历

    返回其层次遍历结果: [ [3], [20,9], [15,7] ]

    五分钟学算法
  • ​LeetCode刷题实战111:二叉树的最小深度

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 打卡群刷题总结0809——二叉树的锯齿形层次遍历

    链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

    木又AI帮
  • 【Leetcode】103. 二叉树的锯齿形层次遍历

    给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    Leetcode名企之路
  • 【python-leetcode103-树的宽度遍历】二叉树的锯齿形层次遍历

    给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    西西嘛呦
  • 14种模式搞定面试算法编程题(PART I)

    面试锦囊系列一直有收到大家的反馈,包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等,非常高兴小破号的这些整理分享能够真正地帮助到大家

    NewBeeNLP

扫码关注云+社区

领取腾讯云代金券