关于数据结构和算法:码不停题算法篇二叉树的层序遍历

题目

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

示例：

二叉树：{val: 3, left: {val: 9}, right: {val: 20, left: {val: 15}, right: {val: 7}}}

返回其层序遍历后果：

[
[3],
[9,20],
[15,7]
]

广度优先遍历和深度优先遍历

深度优先遍历其实相似于树的先序遍历，而广度优先遍历相似树的档次遍历。

上图树的深度优先遍历就是程序 ABDEGCF

办法：从树的根节点开始，沿着树边缘划线，第一次遇到的节点便拜访它。

上图树的广度优先遍历就是程序 ABCDEFG

办法：从树的根节点开始，从上到下，从左到右顺次拜访节点。

题解思路

二叉树的层序遍历其实就是二叉树的广度优先遍历。广度优先遍历即一层一层往下遍历查找，能够设想一下，一个二叉树型数据结构，从上到下遍历，找到以后层级的数据后把以后层级的数据归类到一个数组外面，而后持续往下走，持续分类，这里的要害就是你要始终判断你以后正在查找的树所在的节点和下一次要去的节点地位。每个节点都有一个“指针指向下一个节点”，并且你下一次遍历的层级所领有的节点个数正是你以后遍历的节点领有的指针的个数（left和 right），那么，咱们只有遍历到以后节点，并且判断他身上的“指针”，有的话就push 到下一次要遍历的数组中，以后层遍历完后要把以后层扔掉，因为你下次遍历树的时候就不能反复去遍历了。咦，先遍历到的要先扔掉，这不就是先进先出，队列刚好满足先进先出的条件。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {const res = []; // 定义一个用来装后果的数组
    if (!root) return res; // 树为空的时候返回为空数组
    const queue = []; // 定义一个队列
      queue.push(root); // 把树结构放进队列，先遍历跟节点（最上层）while (queue.length) { // 只有队列中还有下次要遍历的树层构造，就要持续遍历
        const subRes = []; // 寄存每一层级分类好的节点数据
        const len = queue.length; // 树的每一层须要遍历的节点数量
        for(let i = 0; i < len; i++) { // 遍历每一个节点，拿到数据（val）后推动以后层数组（subRes）const node = queue.shift(); // 拿到以后遍历到的节点，并扔掉（解决完就出队列）subRes.push(node.val); // 把以后节点数据拿到推动以后层数组（subRes）if (node.left) queue.push(node.left); // 判断以后节点左指针有没有数据，有的话，放进队列
            if (node.right) queue.push(node.right); // 同理
        }
        res.push(subRes); // 解决分类后的以后层数据放入后果数组中，持续下一次循环
    }
    return res;
};