文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

JavaScript如何实现二叉树层序遍历

2023-07-05 20:10

关注

今天小编给大家分享一下JavaScript如何实现二叉树层序遍历的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

题目描述

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

示例

二叉树:[3,9,20,null,null,15,7],

JavaScript如何实现二叉树层序遍历

返回其层序遍历结果:

JavaScript如何实现二叉树层序遍历

递归实现

代码

  var levelOrder = function(root) {    if (root === null)        return []    let result = [];    let deep = 0;    recursion(root);    function recursion(root) {        deep++;        if (result[deep - 1])            result[deep - 1].push(root)        else            result[deep - 1] = [root]        if (root.left != null)            recursion(root.left)        if (root.right !== null)            recursion(root.right)        deep--        return    }    return result;};let root = {    value: 3,    left: {        value: 9,        left: null,        right: null    },    right: {        value: 20,        left: {            value: 15,            left: null,            right: null        },        right: {            value: 7,            left: null,            right: null        }    }}console.log(levelOrder(root))

思路解析

不得不说递归虽然性能有些不太友好,但是是最容易被想到的方案。我们来一步一步解析一个流程,捋一下代码逻辑。

因为我们使用deep变量标识了当前节点的深度,所以在添加元素时可以添加在对应的位置上。算是得到了要求的数组,但是严格意义上来说,并不算是层级遍历。毕竟层级遍历必须要是使用队列来解决。

图示

JavaScript如何实现二叉树层序遍历

队列实现

代码

var levelOrder = function(root) {    let result = []    if (!root) return result    let queue = [root]    let res = []    let items = []    while (queue.length != 0 || items.length != 0) {        if (!queue.length) {            queue = items            result.push(res)            items = []            res = []        }        let nowRoot = queue.shift()        if (nowRoot) {            res.push(nowRoot.val);            items.push(nowRoot.left)            items.push(nowRoot.right)        }    }    return result};

思路解析

以上就是“JavaScript如何实现二叉树层序遍历”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯