乐闻世界logo
搜索文章和话题
从上到下按层打印二叉树

从上到下按层打印二叉树

乐闻的头像
乐闻

2022年06月18日 11:42· 阅读 481

问题

问题图片

解决方案

  • BFS 广度遍历
javascript
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function (root) { //定义结果集数组 let result = []; if (root) { //因为期望结果是分层数组输出的,区分层次定义父层与子层 let parent = []; let children = []; //暂存当前层的val值 let tmpCache = []; parent.push(root) while (!!parent.length) { //出栈 let current = parent.shift(); tmpCache.push(current.val); //如果当前节点存在,把左右节点暂存到children数组中 if (current.left) { children.push(current.left); } if (current.right) { children.push(current.right); } //如果parent数组长度为0,说明当前层遍历结束,做相应的处理 if (parent.length === 0) { if (tmpCache.length) { result.push(tmpCache); } tmpCache = []; parent = children; children = [] } } } return result; };
标签: