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)


相关推荐

  • Java有哪些编程语言

    Java有哪些编程语言Java作为一种年轻具有活力的编程语言,在最近几年是越来越受到市场的欢迎。它作为面向网络的程序设计语言,用来让程序员创建应用程序。Java是个面向对象的语言,由于它自身具备的入门门槛低等优点。那么,Java编程语言具有什么优点?接下来,就跟着千锋重庆Java的小编一起来了解下吧!1.Java语言是简单的Java语言的语法与C语言和C++语言很接近,使得大多数程序员很容易学习和使用。另一方面,Java丢弃了C++中很少使用的、很难理解的、令人迷惑的那些特性,如操作符重载、多继承、自动的强制类型转换。Jav

  • 企业怎么运营公众号,怎么策划微信集赞活动?「建议收藏」

    企业怎么运营公众号,怎么策划微信集赞活动?「建议收藏」做微信公众号运营,微信活动是微信运营的一个重要内容,吸粉、扩散知名度、发起话题、维护粉丝等运营内容都可以通过微信活动来实现。今天谈谈如何通过微信集赞活动来吸粉。首先确定好活动的主题,如xx店庆、xx开业、xx节日等等其次要提前设置好活动礼品,如满xx赞奖励xx奖品最好可以跟本行业相关,如影楼行业可设置“用户集满100赞获得3张精修照片”;医美行业“用户集满XX赞免费获得一剂瘦脸针”等。奖励条…

  • 据说很快的数据库分页存储过程

    据说很快的数据库分页存储过程

  • vbs代码未结束的字符串常量[通俗易懂]

    vbs代码未结束的字符串常量问题描述:  执行vbs脚本时提示“vbs代码未结束的字符串常量”原因:  vba的BUG,在连接字符串的最后一个字符是单个或多个“行”字(我这里是把“行”字删除就不报错)或者其他原因,会出现未结束的字符串常量解决:  这里使用的是notepadd++在编码或者格式里面将文件编码改成“转为ANSI编码”解决问题…

  • ai的文件怎样将里面的文字转曲_PDF文件置入AI缺少字体

    ai的文件怎样将里面的文字转曲_PDF文件置入AI缺少字体AI文件中文字转曲是什么?怎么转曲?转曲百度百科

  • PHP json 类型「建议收藏」

    PHP json 类型「建议收藏」有时候需要用json的格式返回数据,json是一个很常用的数据传输方式。下面是一个最简单的例子。就是说只需要设置一下文档类型是json的就可以了。‘helloworld’,’2’=>’linuxworld’);$show=j

发表回复

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

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