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

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

题目描述

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

示例

二叉树：[3,9,20,null,null,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

对应数组中添加元素。

然后就到了我们的递归方法

recursion

，

recursion

的参数是当前节点。在

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

的话将当前节点的

val

值

push

如

res

，并获取其左右节点

push

入

items

当

queue

全部取出，说明当前层的节点已经全部遍历完毕，每个节点的

val

在

res

数组中，每个节点的左右节点在

items

中。我们将

items

赋值给

queue

来遍历下一层的全部节点，将

res

整个数组

push

入

result

结果集中，并重置

items

与

res

。

当前层遍历完毕并且当前层全部节点都没有子节点，说明全部节点遍历完毕，跳出循环

返回结果集