关于leetcode:Leetcode-算法题解系列-二叉树的层序遍历

39次阅读

共计 1914 个字符，预计需要花费 5 分钟才能阅读完成。

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

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

题目形容:

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

返回其档次遍历后果：

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

思考某些同学可能比拟少用 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 的子节点存入队列，此时队列残余元素为 []，队列为空完结整个过程 ;

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

除了第一步初始化数据，后续的所有步骤都在 依照第 2 步的规定反复；
察看每一步的取出后果：
1. step2, 取出[3];
2. step3, 取出[9, 20];
3. step4, 取出[15, 17];
这里每一步的取出后果正好就是题设要求的 每一层遍历的后果。
整个过程完结条件，就是 节点队列为空。
这道题讲到这里，其实大抵思路就曾经很清晰了，或者说，其实下面的步骤就曾经是伪代码了(没方法，因为题目自身就十分典型 -_-!)

首先第 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;
 };

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