本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。【当然是基于js进行解答】。
（这道题应该算是二叉树的根底题，倡议还是学一下，不难且经典）

题目相干

  • 原题地址: https://leetcode-cn.com/probl...

  • 题目形容:

    从上到下按层打印二叉树，同一层的节点按从左到右的程序打印，每一层打印到一行，例如，给定二叉树: [3,9,20,null,null,15,7]
       3   / \  9  20    /  \   15   7

    返回其档次遍历后果：

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

    Tips

    思考某些同学可能比拟少用js来刷leetcode，咱们在这里简略介绍下,对于树类型的数据输出,在js里的示意。 形如上题中的内容，给定二叉树的输出，其实并非一个数组，而应该是如下所示: 每个节点是一个object

      const input = {    val: 3,    left: { // left示意以后节点的左侧子节点      val: 9,      left: null, // 对照上图能够看到 节点9没有左右子节点      right: null,    },    right: {      val: 20,      left: {        val: 15, // 对照上图能够看到 节点15没有左右子节点        left: null,         right: null,      },       right: {        val: 7, // 对照上图能够看到 节点7没有左右子节点        left: null,         right: null,      },    }  }

思路解析

这道题比拟根底，其实考的是BFS+层序遍历，怎么说呢？

首先 BFS(Breadth First Search)也就是广度优先搜寻, 指的是在遍历过程，每次总是优先遍历以后节点的所有邻接节点，将其放入一个队列，比方上题的例子：

  • step1: 首先筹备一个空队列（也就是数组） [ ] ，并且把根节点放入数组中,也就是 [3] ；
  • step2: 先取出队列的最后面节点（此时队列只有节点3，取出之后队列置空）， 而后把它的所有邻接节点（在二叉树外面也就是左右子节点）按程序退出拜访队列，所以此时队列元素为 [9  20] ,
  • step3: 持续依照第二步的规定，取出节点9，并把9的子节点放入队列（无子节点）；再把节点20取出，并且把节点20的子节点存入队列，此时队列残余元素为 [15, 7] ;
  • step4: 持续依照第二步规定， 取出节点15， 并把子节点放入队列（无子节点）；再把节点7取出，并且把节点7的子节点存入队列，此时队列残余元素为 []， 队列为空 完结整个过程 ;

仔细观察以上的步骤，你发现了吗？

  1. 除了第一步初始化数据，后续的所有步骤 都在依照第2步的规定反复；

  2. 察看每一步的取出后果：

    1. step2, 取出[3];
    2. step3, 取出[9, 20];
    3. step4, 取出[15, 17];

    这里每一步的取出后果 正好就是题设要求的每一层遍历的后果。

  3. 整个过程完结条件，就是节点队列为空。
    这道题讲到这里，其实大抵思路就曾经很清晰了，或者说，其实下面的步骤就曾经是伪代码了(没方法，因为题目自身就十分典型-_-!)
  • 首先第2步的规定必定就是主函数，因为它全程始终循环；
  • 其次，初始条件/完结条件别离对应的是 根节点入队列，和队列为空；
  • 惟一的难点，在于如何优雅地解决【分层输入】，而这一点 我倡议大家间接看我最初贴地残缺代码。

残缺代码

那么其实就能够间接看代码了:

var levelOrder = function(root) {    if (!root) { // 如果根节点都不存在 那间接完结         return [];    }    const nodes = [root]; // 初始化，对应后面剖析里地初始条件，    const res = [];     while(nodes.length > 0) { // 外层循环 当节点队列为空时完结        const tempRes = [];        let isEmpty = false;        // 【留神点】这个内循环 也就是解决分层输出地精华所在，大家能够认真琢磨下这个循环条件        // 尝试答复这里为什么不采纳 “i=0 ；i<nodes.length； i++”的模式        for(let i = nodes.length;i > 0 ; i--) {             const node = nodes.shift();            tempRes.push(node.val);            if(node.left) {                nodes.push(node.left);            }            if(node.right) {                nodes.push(node.right);            }        }        res.push(tempRes);           }    return res; };

好了整体的题目算是根底题， 就不画动态图了（画图很耗时）， 然而想两个问题给大家思考：

  1. 也就是代码块里的问题，为什么内循环的条件不是 i=0 ；i<nodes.length； i++ ？ 如果是，会怎么样？
  2. 如果本道题演变成输入深度优先遍历的后果，外围要点要怎么改变？
    如果可能答复出下面的两个问题，那基本上就了解了这个知识点！