大家好,又见面了,我是你们的朋友全栈君。
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例 二叉树:[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
对应数组中添加元素。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
。发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/143626.html原文链接:https://javaforall.cn
如果您是在找激活码,但输入激活码后激活失败,最新激活码地址:https://javaforall.cn/127239.html