JavaScript——二叉树层序遍历

JavaScript——二叉树层序遍历题目描述给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。示例二叉树:[3,9,20,null,null,15,7], 3/\920/\157返回其层序遍历结果:[[3],[9,20],[15,7]]递归实现代码varlevelOrder=function(root){if(root===null)return[]l

大家好,又见面了,我是你们的朋友全栈君。

题目描述

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

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

  	3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果:

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

递归实现

代码

  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))

思路解析

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

  • 第一步判断root是否是null,如果为空我们直接返回空数组即可,如果不为空继续我们的代码运行
  • 第二步声明了两个变量result用来承接最后的数组,并作为最后的结果返回。deep用来表示当前节点的层级,方便我们向result对应数组中添加元素。
  • 然后就到了我们的递归方法recursionrecursion的参数是当前节点。在recursion中现实节点深度加一,我们要注意这个深度的流程是,对于二叉树的结构,向下递归一层deep加一,向上return一层deep减一。
  • 判断result对应该层的数组元素是否存在,如果不存在直接等于[root],如果存在则选择push方式添加当前root
  • 添加完当前节点就需要判断,当前节点的左节点是否存在,如果存在将当前节点的左节点作为参数递归调用当前recursion函数,如果不存在则跳过
  • 当前节点的右节点是否存在,如果存在将当前节点的右节点作为参数递归调用当前recursion函数,如果不存在则跳过
  • 当左节点右节点都不存在则深度减一并向上返回,或者节点的左节点右节点都已经遍历完毕也是同样深度减一并向上返回。
  • 当全部执行完毕,返回result

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

图示

请添加图片描述

队列实现

代码

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
};

思路解析

  • 同样result用来承接最后结果,queue承接当前层的全部节点,作为队列去使用,res去承接当前层queue中取出的节点的val值,items用来承接下一层的全部节点
  • 判断root是都为空,和上面一样就不详细解析
  • 进入循环,只有当当前层的节点遍历完毕并且没有下一层节点的情况下才会跳出循环
  • 当前层节点没有全部取出(queue的长度不为0),则取出queue中的第一个节点,节点不为null的话将当前节点的valpushres,并获取其左右节点pushitems
  • queue全部取出,说明当前层的节点已经全部遍历完毕,每个节点的valres数组中,每个节点的左右节点在items中。我们将items赋值给queue来遍历下一层的全部节点,将res整个数组pushresult结果集中,并重置itemsres
  • 当前层遍历完毕并且当前层全部节点都没有子节点,说明全部节点遍历完毕,跳出循环
  • 返回结果集
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/143626.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 看一下MySQL索引类型「建议收藏」

    看一下MySQL索引类型「建议收藏」一、简介MySQL目前主要有以下几种索引类型:1.普通索引2.唯一索引3.主键索引4.组合索引5.全文索引二、语句CREATETABLEtable_name[col_namedatatype][unique|fulltext][index|key][index_name](col_name[length])[asc|desc]1.unique|fulltext为可选参数,分别表示唯一索引、全文索引2.index和key为同义词,两者作用相同,用来指定创建索引3.co

  • NAT网关之SNAT进阶使用(一)SNAT POOL

    NAT网关之SNAT进阶使用(一)SNAT POOL

  • python 元类编程_python抽象基类

    python 元类编程_python抽象基类前言通常我们创建类都是使用class类名,但是小伙伴们有没有想过,类是由谁来创建的呢,python中常说的万物皆对象,对象是由类创建的,那类本身也可以看做是对象,类可以由元类type创建type

  • 火车头采集器在线发布模块制作教程视频_火车头采集器收费与免费的区别

    火车头采集器在线发布模块制作教程视频_火车头采集器收费与免费的区别在线发布模块,就是采集器通过网站后台,发布文章,也就是说,把你手动在网站后台发布文章的整个过程包含登录网站后台,选择栏目,到后面的发布文章,这些步骤写到采集器里面,就是在线发布模块,然后规则采集到的值就通过标签名传递给在线发布模块,把数据提交到网站里去。我们借助抓包工具Fiddler(下载地址:http://www.locoy.com/Down/RelatedSoft/Fiddle

  • 什么是跨域?怎么解决跨域问题?「建议收藏」

    什么是跨域?怎么解决跨域问题?「建议收藏」什么是跨域?跨域,指的是浏览器不能执行其他网站的脚本。它是由浏览器的同源策略造成的,是浏览器对javascript施加的安全限制。所谓同源是指,域名,协议,端口均相同,不明白没关系,举个栗子:http://www.123.com/index.html调用http://www.123.com/server.php(非跨域)http://www.123.com

  • TDD与FDD技术对比

    TDD与FDD技术对比双工(Duplex)是一种在单一通信信道上实现双向通信的过程,包括两种类型,分别为半双工和全双工。  在半双工系统中,通信双方使用单一的共享信道轮流发送数据。双向广播就采用了这种方式。在一方发送数据时,另一方只能收听。数据发送方通常会发出“Over”的信号,表明本方数据发送结束,对方可以开始发送数据。在实际网络中,两台计算机可以使用一根通信电缆来轮流收发数据。  全双工则是指同时的双向通信

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号