【算法】二叉树的层序遍历

题目

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

示例：

二叉树：{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;
};