一.题目

LeetCode-102.二叉树的层序遍历

描述:逐层从左到右打印所有节点
Input:
[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output:
[
[3],
[9,20],
[15,7]
]
思路：

  • 用队列存储每一层的节点，扫描当前层的同时把下一层节点加入队列
  • 从队列中拿出一个节点并添加到该层临时结果集中后称为扫描了这个节点
  • 记录每层节点序列的长度：假设第i层已经放入队列了，开始扫描第i层之前记录队列的size，这个size就是第i层的序列长度

具体实现：

  • 假设树的第 i 层节点已经以从左到右的排列方式依次添加到queue中，而且此时queue中只存在第 i 层的节点
  • 构建第 i 层临时结果集的方式？队头依次出队然后以 “尾插法“ 插入到 第i层临时结果集
  • 将第 i 层临时结果集添加到全局结果集的方式？ 以 “尾插法” 插入到 全局结果集
  • 将第 i+1 层节点添加到 queue中的方式? 对队头依次出队的元素 按照 “left->right” 的顺序依次将其不为空的孩子节点 添加到queue中

LeetCode-103. 二叉树的锯齿形层序遍历

描述: 对二叉树，返回锯齿形层序遍历（先从左往右，再从右往左）
Input: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output:
[
[3],
[20,9],
[15,7]
]
思路：类似于leetcode102
假设二叉树的第i层节点以从左到右的顺加入到queue中，和常规层次遍历相比

  • 将第 i+1 层节点添加到 queue中的方式? 不变
  • 构建第 i 层临时结果集的方式？

发生变化， 奇数层 以 “尾插法” 添加到临时结果集，偶数层以 “头插法” 添加到临时结果集

  • 将第 i 层临时结果集添加到全局结果集的方式？ 不变

  • 如何判断每一层该用 “尾插” 还是 “头插” 将节点从队列加入该层临时结果集呢？

    • （1）方法1：记录层数count，count %2判断奇偶，奇数 “尾插”，偶数 “头插”
    • （2）方法2：设置一个flag，第一层初始化为true，为true采用 “尾插” ，为false采用 “头插”，每层节添加到临时结果集后，置反flag

      LeetCode-107. 二叉树的层序遍历 II

      描述：返回二叉树的节点值自底向上的层序遍历
      Input: [3,9,20,null,null,15,7],
      3
      / \
      9 20
      / \
      15 7
      Output:
      [
      [15,7],
      [9,20],
      [3]
      ]
      思路：
      假设二叉树的第i层节点以从左到右的顺加入到queue中，和常规层次遍历相比

  • 将第 i+1 层节点添加到 queue中的方式? 不变

  • 构建第 i 层临时结果集的方式？ 不变
  • 将第 i 层临时结果集添加到全局结果集的方式？

变化了，以 “头插法” 方式将第 i 层临时结果集加入到全局结果集

LeetCode-116. 填充每个节点的下一个右侧节点指针

描述：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点，将每个节点的 next 指针指向其下一个右侧节点，右侧节点不存在时将 next 指针设置为 NULL，只能使用常量级额外空间

2-1 广度优先搜索BFS - 图1
思路：假设第i层的所有节点都已经从左到右连接成一个链表了，如何将第i+1层的所有节点连接成链表呢？

  • 顺着第i层的头节点head可遍历完第i层的所有节点，通过访问每个节点的left、right指针可以得到其左右孩子，所以遍历完第i层节点就可以将第i+1层的所有节点链接成链表
  • 在构建第 i+1 层链表时一定要持有第 i 层头节点

  • 在建立每层的链表时，对 该层的 头节点 需要特殊处理

    1. 头节点要传给下一层
    2. 如果使用指针p来尾插法建立链表，start表示第i+1层头节点，node表示当前遍历的节点
      1. // 保存第i+1层头节点传给第i+2层
      2. if(start==null){
      3. start = node;
      4. }
      5. // p不为空才可以尾插
      6. if(p!=null){
      7. p.next = node; 
      8. }
      9. // p为空,p初始化头节点
      10. // p不为空,p移动到下一个节点
      11. p = node;

      LeetCode-130. 被围绕的区域

      描述：给一个 m x n 的矩阵 board，由若干字符'X'和'O'填充，找到所有被 'X'围绕的区域，并将这些区域里所有的 'O'用 'X' 填充。
      例子：
      Input
      board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
      2-1 广度优先搜索BFS - 图2
      Output
      [[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
      解释：任何边界上的 'O' 以及和边界上的 '0'相连的 '0'都不会被填充为 'X'。
      思路：
      从四个边界 “上、左、下、右”的所有 '0'出发 搜索所有于其相连的 ‘0'，将这些 '0'（包括边界上的 '0')都替换为 'B'，然后重新扫描整个矩阵，将 所有的 'O'替换为 'X'，将 'B' 替换为 '0'
      实现：

  • 以BFS（借助queue）或 DFS（递归）的方式搜索

  • 对每个位置向 “上、左、下、右” 四个方向延申，判断延申的每个位置的坐标是否在矩阵中
  • 延申的每个合法新位置的值不是 '0' 时停止继续延申
  • 是 'O'时，将该位置的值替换为 'B'，并从该新位置继续向四个方向延申

LeetCode-133. 克隆图

描述：给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆），图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）

  1. class Node {
  2.     public int val;
  3.     public List<Node> neighbors;
  4. }


2-1 广度优先搜索BFS - 图3

思路：

  • 什么是一个节点的深度copy？

深拷贝图的一个节点包括（1）new 一个新节点和 老节点有相同的value （2）新节点的邻接表都是老节点邻接表的copy

  • 拷贝每个节点都分为两个步骤，先copy老节点的val，然后copy老节点的邻接表
  • 用map保存 {oldNode:newNode}的关系，采用DFS或 BFS（借助queue）来完成两步骤的深度copy
  • 关键点是不能对同一个老节点深度copy两次
    1. 因为输入是无向联通图，所以一定会遍历到同一老节点两次
    2. 第一次我们深度copy时，将 {oldNode:newNode}的关系保存到了map，当第二次遍历到同一个老节点时如果发现map中已经存在这个老节点的key，说明该老节点已经被深度copy过了

代码：

  1.     // BFS
  2.     public Node cloneGraph(Node node) {
  3.         if(node==null){
  4.             return null;
  5.         }
  6.         Map<Node, Node> map = new HashMap<>();
  7.         Node copyNode = new Node(node.val);
  8.         // queue的老节点，需要将其邻接表copy一份并添加到该老节点的copy的邻接表中
  9.         Queue<Node> queue = new LinkedList<>();
  10.         queue.add(node);
  11.         map.put(node, copyNode);
  12.         while(queue.size()>0){
  13.             Node item = queue.poll();
  14.             Node itemCopy = map.get(item);
  15.             itemCopy.neighbors = new ArrayList<>();
  16.             for(Node child: item.neighbors){
  17.                 // map中存在该老节点时，说明该老节点已经被深度copy过了
  18.                 // 则不需要添加到queue中
  19.                 if(map.containsKey(child)){
  20.                     itemCopy.neighbors.add(map.get(child));
  21.                 }else{
  22.                     Node childCopy = new Node(child.val);
  23.                     map.put(child, childCopy);
  24.                     itemCopy.neighbors.add(childCopy);
  25.                     // child需要处理邻接点
  26.                     queue.add(child);
  27.                 }
  28.             }
  29.         }
  30.         return copyNode;
  31.     }
  1.     // DFS
  2.     public Node cloneGraph(Node node) {
  3.         if(node==null){
  4.             return null;
  5.         }
  6.         Map<Node, Node> map = new HashMap<>();
  7.         Node copyNode = new Node(node.val);
  8.         map.put(node, copyNode);
  9.         cloneGraph(node, copyNode, map);
  10.         return copyNode;
  11.     }
  12.     // 把node的邻接表copy给copyNode
  13.     public void cloneGraph(Node node, Node copyNode, Map<Node, Node> map){
  14.         if(node.neighbors==null){
  15.             return;
  16.         }
  17.         List<Node> copyNodeNeighbors = new ArrayList<>();
  18.         copyNode.neighbors = copyNodeNeighbors;
  19.         if(node.neighbors.size()==0){
  20.             return;
  21.         }
  22.         for(Node item: node.neighbors){
  23.             if(map.containsKey(item)){
  24.                 copyNodeNeighbors.add(map.get(item));
  25.             }else{
  26.                 Node tempNode = new Node(item.val);
  27.                 map.put(item, tempNode);
  28.                 copyNodeNeighbors.add(tempNode);
  29.                 cloneGraph(item, tempNode, map);
  30.             }
  31.         }
  32.     }

LeetCode-199. 二叉树的右视图

描述：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
例子：
Input：[1,2,3,null,5,null,4]
1 <—-
/ \
2 3 <—-
\ \
5 4 <—-
Output：[1, 3, 4]
思路：
（1）BFS:常规层次遍历，从第一层到最后一层取全局结果集的每层的最右侧节点组成序列即可

（2）DFS：每次优先访问右子树，右子树为空时访问左子树，一直递归访问到叶子节点。
2-1 广度优先搜索BFS - 图4

LeetCode-200. 岛屿数量

描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
例子：
Input：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
Output：1
思路：从边缘往里搜索
遍历矩阵，对矩阵中每个为1的元素，向四周搜索所有与其相连的1（为1连通图），每一个为1的连通图就是一个岛屿，每搜索了一个岛屿就将该岛屿的所有位置的值置为'0'，得到所有岛屿的数量即可

  1. 使用BFS/DFS都可以，向四个方向 “上、左、下、右” 延申
  2. 对每个延申的新位置，都注意判断是否超出矩阵边界
  3. 每个延申的合法位置的值，为1则将其置0，从该位置继续向四周延申
  4. 每个延申的合法位置的值，为0则停止搜索

LeetCode-207. 课程表

描述：
有 numCourses 门课程，记为 0 到 numCourses - 1 ，课程之间有先修关系，先修关系以数组 prerequisites 给出，比如 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false

拓扑排序问题
获取一个拓扑排序序列的过程就是从入度为0的节点开始不断从图中删除该节点和该节点的所有出边，然后继续从新的出度为0的节点执行删除节点和边的操作，如果最后能所有节点删除，则说明有拓扑排序序列，节点删除的序列就是一个拓扑排序序列
思路：

  1. 构建每个节点的邻接表
  2. 构建入度数组inDegree；比如inDegree[0] = 2表示课程0有两个先修课程
  3. 获取拓扑序列，将入度为0的所有节点加入queue并执行下列循环直到queue为空
    1. queue出队一个节点node并将node加入结果集（删除节点的过程，脑海中脑补）
    2. 遍历node的邻接表，将node的每个邻节点的入度减少1（inDegree的值减1）
    3. 将新的入度为0的节点加入queue
  4. 如果最后的结果集的大小等于图的节点数说明拓扑排序存在。

    LeetCode-210. 课程表 II

    描述：给必修的课程数量 n，和先修关系数组 prerequisites，求一个拓扑排序序列（任意一个即可）
    输入: 2, [[1,0]]
    输出: [0,1]
    解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
    思路：同leetcode-207

LeetCode-310. 最小高度树

描述：给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi]表示树中节点 ai 和 bi之间存在一条无向边，可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树,请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
例子
输入：n = 4, edges = [[1,0],[1,2],[1,3]]

2-1 广度优先搜索BFS - 图5

输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
思路：从边缘往里搜索
类似于 “leetcode-200 岛屿数量” ，我们将树看作是从最外层向里一圈一圈形成的，然后从最外层开始一圈一圈剪去，最后剩下的那一圈就是答案序列
实现：

  • 构建每个节点的邻接表
  • 构建每个节点的出度数组 outDegree，比如outDegree[0]=1表示 节点0和1个节点相邻
  • 剪取外层节点，将所有出度为1（最外圈）的节点加入queue，并执行下列循环：
    1. 创建一个tempList存储该圈节点
    2. 出队一个节点node并将node加入tempList
    3. 遍历node的邻接表，对node的每个邻接点的outDegree都减1
    4. 将新的outDegree值为1的节点加入queue
  • 最后的tempList就是答案

LeetCode-417. 太平洋大西洋水流问题

描述：m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界，水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动，请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
例子
Input:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5)
~ 3 2 3 (4) (4)
~ 2 4 (5) 3 1
~ (6) (7) 1 4 5
~ (5) 1 1 2 4
大西洋
Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元)

思路：从边缘往里搜索
类似于 “leetcode-200 岛屿数量”，从上、左边界向里 “逆向”(延申的坐标高度大于等于出发的高度）搜索所有可以到达 “太平洋” 的位置，从下、右边界向里 “逆向”(延申的坐标高度大于等于出发的高度）搜索所有可以到达 “大西洋” 的位置，
实现：

  • 用两个boolean矩阵分别表示可以到达 “太平洋” 和 “大西洋” 的位置
  • 对延申的位置注意判断是否超过输入矩阵边界
  • 延伸时符合逆向要求的坐标置true，并从该坐标继续向四周延申
  • 延伸时符合不逆向要求的坐标置false(默认就是false)，并从该坐标继续向四周延申
  • 注意对于同一个洋来说，比如 “太平洋” 搜索了上边界后，搜索左边界时可以从第1行开始，因为第0行已经被搜索过了

LeetCode-429. N 叉树的层序遍历
描述：给定一个 N 叉树，返回其节点值的层序遍历

class Node {
    public int val;
    public List<Node> children;
}

思路：和常规二叉树层序遍历一样，只是将left->right 孩子加入queue换成了children list加入queue

二.总结

1.层序遍历系列

leetcode-102.二叉树的层序遍历

leetcode-103.二叉树的锯齿形层序遍历

leetcode-107.二叉树的层序遍历 II

2.从边缘向里搜索系列

leetcode-130.被围绕的区域

leetcode-310.最小高度树

leetcode-417.太平洋大西洋水流问题