二叉树层序遍历

Question

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

注意：层序遍历返回的是一个二维数组

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

var levelOrder = function(root) {
    const queue = []
    const ans = []
    if(root!=null)  
        queue.push(root)
    let index = 0                   //记录第几层
    while(queue.length!=0){
        ans.push([])
        let len = queue.length      //记录该层有几个节点
        for(let i=0;i<len;i++){
            let p = queue.shift()   //shift() 方法从数组中删除第一个元素，并返回该元素的值
            ans[index].push(p.val)
            if(p.left!=null)   queue.push(p.left)
            if(p.right!=null)   queue.push(p.right)
        }
        index++
    }
    return ans
};

二叉树层序遍历 ​

二叉树层序遍历