首页 > 试题广场 >

求二叉树的层序遍历

[编程题]求二叉树的层序遍历

热度指数：250651 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]

提示:

0 <= 二叉树的结点数 <= 1500

示例1

输入

{1,2}

输出

[[1],[2]]

示例2

输入

{1,2,3,4,#,#,5}

输出

[[1],[2,3],[4,5]]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Javascript

nicole27

function levelOrder( root ) {
    // write code here
    if(root==null) return [[]];
    let queue = [];
    let res = [];
    queue.push(root);
    while(queue.length>0){
        let len = queue.length;
        let arr=[];
        while(len--){
            let node = queue.shift();
            arr.push(node.val);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        if(arr.length) res.push(arr);
    }
    return res;
}

发表于 2022-03-25 13:41:18 回复(0)

Javascript

美英

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder( root ) {
    // write code here
    //{1,2,3,4,#,#,5}
    //第一步，为空返回空list
    var list = [];
    if(!root){
        return list;
    }
    
    //第二步，定义结果集，root压入list
    var res=[];
    list.push(root);
    
    //第三步，list长度>0
    while(list.length>0){
        //3-1 临时的数组存每层的节点值
        let arr=[];
        
        //3-2 定义len 等于list长度
        let len = list.length;//list的长度
        //3-3 终止条件
        while(len){
            //删除第一个节点,并返回第一个节点
           let node = list.shift();
           
           //临时数组存储节点
           arr.push(node.val);
           if(node.left){//存在左子树，左子树压入list
               list.push(node.left);
           }
           if(node.right){//存在右子树,右子树压入list
               list.push(node.right);
           }
           //len 长度对应减1
           len--;
        }
        //每层节点急压入结果集
        res.push(arr);
    }
    
    //最后，return 结果
    return res;
}
module.exports = {
    levelOrder : levelOrder
};

发表于 2021-12-12 09:45:57 回复(0)

Javascript

飞牛cz

发表于 2021-10-10 13:40:43 回复(0)

Javascript

牛客809451450号

function levelOrder( root ) {
// write code here
var res = [[]]
if (!root) { return [] }
function recurse ( root, level ) {
if (!root) { return null }
res[level].push(root.val)
if (level == res.length - 1 && (root.left || root.right)) {
res = res.concat([[]])
}
recurse(root.left, level+1)
recurse(root.right, level+1)
}
recurse(root, 0)
return res
}

发表于 2021-08-19 21:00:13 回复(0)

Javascript

牛客81899409号

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder( root ) {
    // write code here
    if(!root) return [];
    let queue = [root]; // 建立queue，将跟元素放进去
    let twoArr = [] 
    while(queue.length) {
        let oneArr = []; 
        let queueLength = queue.length;
        while(queueLength) {
            let node = queue.shift(); // 去掉根节点，此时queue里的元素就是下一层的所有节点
            node.left && queue.push(node.left); // 找根节点的左右两个子节点
            node.right && queue.push(node.right);
            queueLength--;
            oneArr.push(node.val); // 将结果存到一个一维向量里
        }
        twoArr.push(oneArr); // 再把这个一维向量存到二维向量里
    }
    return twoArr;
}
module.exports = {
    levelOrder : levelOrder
};

发表于 2021-08-19 13:58:49 回复(0)

Javascript

小菜鸡的菜

function levelOrder( root ) {
var ret = []
var stack = []
// write code here
if(!root){
return ret
}
stack.push(root)
while(stack.length){
var n = stack.length
var arr = []
for(var i=0;i<n;i++){
var temp = stack.shift()
arr.push(temp.val)
if(temp.left){
stack.push(temp.left)
}
if(temp.right){
stack.push(temp.right)
}
}
ret.push(arr)
}
return ret
}

发表于 2021-08-12 17:14:42 回复(0)

Javascript

web-hu

function levelOrder( root ) {
    // write code here
    let levelList = []
    if(!root) return levelList
    const linkList = []
    levelList.push(root)
    while(levelList.length){
        const currentArr = [], currentLevelList = []
        for(let index =0;index<levelList.length;index++){
            currentArr.push(levelList[index].val)
            if(levelList[index].left){
                currentLevelList.push(levelList[index].left)
            }
            if(levelList[index].right){
                currentLevelList.push(levelList[index].right)
            }
        }
        levelList = currentLevelList
        linkList.push(currentArr)
    }
   return linkList
}
module.exports = {
    levelOrder : levelOrder
};

把二叉树数据看成层级划分，从顶层开始依次从左到右顺序记录每层数据，将数据遍历即可得到结果

发表于 2021-08-06 07:55:11 回复(0)

Javascript

小试牛刀，测试一下

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */

function levelOrder( root ) {
    if(!root) {
        return [];
    }
    let levelList = [root];
    let result = [];
    while(levelList.length) {
        let temp = [];
        let length = levelList.length;
        for(let i = 0; i < length; i++) {
            let arr = levelList.shift();
            temp.push(arr.val);
            if(arr.left) levelList.push(arr.left);
            if(arr.right) levelList.push(arr.right);
        }
        result.push(temp);
    }
    return result;
}
module.exports = {
    levelOrder : levelOrder
};

用js实现的话，需要对数组操作函数比较了解，不然容易引起bug。

发表于 2021-07-28 16:25:40 回复(0)

Javascript

桃丨思凡

发表于 2021-07-16 21:47:44 回复(0)

JavaScript

pro给一个offer吧

// 使用队列的先进先出结构
function levelOrder( root ) {
    if(!root) return [];
    let res = [];//存放结果的数组
    let queue = [root];
    while(queue.length) {
        let subRes = [];//每一层的子数组
        let len = queue.length;
        for(let i=0; i<len; i++) {
            let temp = queue.shift();
            subRes.push(temp.val);
            if(temp.left) queue.push(temp.left);
            if(temp.right) queue.push(temp.right);
        }
        res.push(subRes);
    }
    return res;
}
module.exports = {
    levelOrder : levelOrder
};

发表于 2021-06-13 19:39:23 回复(0)

JavaScript

splwany

function levelOrder( root ) {
    const res = [];
    if (!root) return res;
    const queue = [root];
    while (queue.length > 0) {
        res.push(queue.map(i => i.val));
        let len = queue.length;
        while (len) {
            const cur = queue.shift();
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
            len--;
        }
    }
    return res;
}

发表于 2021-04-02 17:10:59 回复(0)

JavaScript

牛客193000445号

/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/

/**
*
* @param root TreeNode类
* @return int整型二维数组
*/
function levelOrder( root ) {
let result = []
if(!root) return result
let arr = [root]
while(arr.length > 0){
let tempArr = []
let values = []
for(let i = 0; i < arr.length; i++){
let item = arr[i]
values.push(item.val)

if(item.left)
tempArr.push(item.left)

if(item.right)
tempArr.push(item.right)
}
arr = tempArr
result.push(values)
}
return result
}
module.exports = {
levelOrder : levelOrder
};

发表于 2020-12-17 16:43:14 回复(0)

JavaScript

别卷啦！

function levelOrder( root ) {
    // write code here
    const res =[]
    const traversal = (root,depth) =>{
        if(root !== null){
            if(!res[depth]){
                res[depth] = []
            }
            traversal(root.left, depth+1)
            res[depth].push(root.val)
            traversal(root.right,depth+1)
        }
    }
    traversal(root,0)
    return res
}

发表于 2020-12-14 16:46:58 回复(0)

JavaScript

牛客235375941号

function levelOrder( root ) {
    // write code here
    let levels = []
    if (!root) return levels
    function walk (node, level) {
        if (levels.length === level){ 
            levels.push([])
        }
        levels[level].push(node.val)
        if (node.left) walk(node.left, level+1)
        if (node.right) walk(node.right, level+1)
    }
    walk(root, 0)
    return levels
}

发表于 2020-10-16 20:03:59 回复(0)

JavaScript

牛客952602447号

function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}

function levelOrder(root) {

// 非空判断😘

if(!root){return []}

// 定义一个队列，初始化推入根节点和他的层级😄

let queue = [[root, 0]]

let res = []

// 队列有长度的情况下进行循环

while(queue.length){

let [n, l] = queue.shift()

// 判断res[l]是否有值

if(!res[l]){
res.push([n.val])
}else{
res[l].push(n.val)
}
if(n.left){queue.push([n.left, l+1])}
if(n.right){queue.push([n.right, l+1])}
}
return res
}
module.exports = {
levelOrder : levelOrder
};

发表于 2020-09-10 16:50:33 回复(0)