力扣 (LeetCode)-104. 二叉树的最大深度，图

达达前端

发布于 2021-03-22 11:30:07

5970

发布于 2021-03-22 11:30:07

文章被收录于专栏：达达前端达达前端

哪吒人生信条：如果你所学的东西处于喜欢才会有强大的动力支撑。

每天学习编程，让你离梦想更新一步，感谢不负每一份热爱编程的程序员，不论知识点多么奇葩，和我一起，让那一颗四处流荡的心定下来，一直走下去，加油，2021加油！欢迎关注加我vx:xiaoda0423，欢迎点赞、收藏和评论

时间：3 月 1 日～ 3 月 13 日

力扣 (LeetCode)-两数之和,有效的括号,两数相加｜刷题打卡-3月1日
力扣 (LeetCode)-合并两个有序链表,删除排序数组中的重复项,JavaScript笔记｜刷题打卡-3月2日
力扣 (LeetCode)-最大子序和,JavaScript数据结构与算法（数组）｜刷题打卡-3月3日
针对CSS说一说｜技术点评-3月4日
力扣 (LeetCode)-栈,括号生成｜刷题打卡-3月5日
原来也没有那么难！Vue商城开发 | 技术点评-3月6日
力扣 (LeetCode)-加一，队列｜刷题打卡-3月7日
JavaScript数据结构之链表 | 技术点评-3月8日
JavaScript的数据结构-集合｜技术点评-3月9号
力扣 (LeetCode)-合并两个有序数组,字典,散列表｜刷题打卡-3月10号
力扣 (LeetCode)-对称二叉树,树｜刷题打卡

前言

如果这篇文章有帮助到你，给个❤️关注，❤️点赞，❤️鼓励一下作者，接收好挑战了吗？文章公众号首发，关注 程序员哆啦A梦 第一时间获取最新的文章

❤️笔芯❤️~

栈，队列，链表，集合，字典和散列表，树

图

图是网络结构的抽象模型。
图是一组由边连接的节点（或顶点）
一个图G=(V,E)由V:一组顶点，E:一组边，连接V中的顶点
由一条边连接在一起的顶点称为相邻顶点
一个顶点的度是其相邻顶点的数量
路径是顶点v1, v2,…,vk的一个连续序列，其中vi和vi+1是相邻的
简单路径要求不包含重复的顶点（环也是一个简单路径）
如果图中不存在环，则称图为无环的，如果图中每两个顶点间都存在路径，则该图是连通的
图可以是无向的（边没有方向）或是有向的（有向图）
如果图中每两个顶点间在双向上都存在路径，则该图是强连通的
图还可以是未加权的或是加权的

邻接矩阵

每个节点都和一个整数相关联，该整数将作为数组的索引。

image.png

如果索引为i的节点和索引为j的节点相邻，则array[i][j] === 1，否则array[i][j] === 0

邻接表

邻接表的动态数据结构来表示图
邻接表由图中每个顶点的相邻顶点列表所组成

image.png

关联矩阵

使用关联矩阵来表示图
在关联矩阵中，矩阵的行表示顶点，列表示边
关联矩阵用于边的数量比顶点多的情况下，以节省空间和内存

创建Graph类

function Graph(){
// 使用一个数组来存储图中所有顶点的名字
 var vertices = [];
 // 一个字典来存储邻接表
 var adjList = new Dictionary();
}

字典将会使用顶点的名字作为键，邻接顶点列表作为值

一个用来向图中添加一个新的顶点
一个方法用来添加顶点之间的边

this.addVertex = function(v){ 
// 将该顶点添加到顶点列表中
 vertices.push(v); //法接受顶点v作为参数
 adjList.set(v, []); 
 //在邻接表中，设置顶点v作为键对应的字典值为一个空数组 
};

this.addEdge = function(v, w){ 
// 接受两个顶点作为参数
 adjList.get(v).push(w); 
 //通过将w加入到v的邻接表中，我们添加了一条自顶点v到顶点w的边 
 adjList.get(w).push(v); //添加一条自w向v的边 
};

var graph = new Graph(); 
var myVertices = ['A','B','C','D','E','F','G','H','I']; 
//创建了一个数组，包含所有我们想添加到图中的顶点 

for (var i=0; i<myVertices.length; i++){ 
//遍历vertices数组并将其中的值逐一添加到我们的图中

 graph.addVertex(myVertices[i]); 
} 

graph.addEdge('A', 'B'); 
//添加想要的边
graph.addEdge('A', 'C'); 
graph.addEdge('A', 'D'); 
graph.addEdge('C', 'D');

实现一下Graph类的toString方法

this.toString = function(){ 
 var s = ''; // 构建了一个字符串
 
 for (var i=0; i<vertices.length; i++){ //迭代vertices数组列表
 
 s += vertices[i] + ' -> '; 
 //将顶点的名字加入字符串中
 var neighbors = adjList.get(vertices[i]); //取得该顶点的邻接表
 
 for (var j=0; j<neighbors.length; j++){ //迭代该邻接表
 //将相邻顶点加入我们的字符串
 s += neighbors[j] + ' '; 
 } 
 // 邻接表迭代完成后，给我们的字符串添加一个换行符
 s += '\n'; //{13} 
 } 
 return s; 
};

图的遍历

广度优先搜索（Breadth-First Search，BFS）
深度优先搜索（Depth-First Search，DFS）

广度优先搜索算法和深度优先搜索算法，只有一点不同，那就是待访问顶点列表的数据结构。

图遍历的思想方法（指出第一个被访问的顶点）

必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索

深度优先搜索算法，数据结构是栈，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问

广度优先搜索算法，数据结构是队列，通过将顶点存入队列中，最先入队列的顶点先被探索

白色，表示该顶点还没有被访问
灰色，表示该顶点被访问过，但并未被探索过
黑色，表示该顶点被访问过且被完全探索过

务必访问每个顶点最多两次
广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层（就是先宽后深地访问顶点）

示例：

// 执行此初始化操作
var initializeColor = function(){ 
// 都需要标注被访问过的顶点
 var color = []; 
 // 使用一个辅助数组color
 
 for (var i=0; i<vertices.length; i++){ 
 color[vertices[i]] = 'white'; //开始执行时，所有的顶点颜色都是白色
 } 
 return color; 
};

// 接受一个顶点作为算法的起始点 接受一个回调
this.bfs = function(v, callback){ 
 var color = initializeColor(), 
 //用initializeColor函数来将color数组初始化为white 
 
 queue = new Queue(); //还需要声明和创建一个Queue实例
 
 queue.enqueue(v); //将会存储待访问和待探索的顶点
 
 while (!queue.isEmpty()){ //如果队列非空 
 var u = queue.dequeue(), //将通过出队列 
 // 操作从队列中移除一个顶点
 neighbors = adjList.get(u); 
 //取得一个包含其所有邻点的邻接表
 
 color[u] = 'grey'; //该顶点将被标注为grey
 // 表示我们发现了它，但未完成对其搜索
 
 for (var i=0; i<neighbors.length; i++){ //每个邻点 
 var w = neighbors[i]; //取得其值
 
 if (color[w] === 'white'){ 
 //如果它还未被访问过
 color[w] = 'grey'; //则将其标注为我们已经发现了它 
 queue.enqueue(w); //将这个顶点加入队列中 
 } 
 } 
 color[u] = 'black'; 
 // 当完成探索该顶点和其相邻顶点后，我们将该顶点标注为已探索过的 
 if (callback) { //如果我们传递了回调函数
 callback(u); // 会用到它
 } 
 } 
};

使用BFS寻找最短路径

题：给定一个图G和源顶点v，找出对每个顶点u，u和v之间最短路径的距离（以边的数量计）。

思路：对于给定顶点v，广度优先算法会访问所有与其距离为1的顶点，接着是距离为2的顶点，以此类推。

从v到u的距离d[u]；
前溯点pred[u]，用来推导出从v到其他每个顶点u的最短路径。

this.BFS = function(v){ 
 var color = initializeColor(), 
 queue = new Queue(), 
 d = [], //声明数组d
 // 表示距离
 
 pred = []; //及pred数组来表示前溯点
 
 queue.enqueue(v); 
 for (var i=0; i<vertices.length; i++){
 d[vertices[i]] = 0; //图中的每一个顶点，用0来初始化数组d 
 pred[vertices[i]] = null; //用null来初始化数组pred 
 } 
 
 while (!queue.isEmpty()){ 
 var u = queue.dequeue(), 
 neighbors = adjList.get(u); 
 color[u] = 'grey'; 
 
 for (i=0; i<neighbors.length; i++){ 
 var w = neighbors[i]; 
 if (color[w] === 'white'){ 
 color[w] = 'grey'; 
 d[w] = d[u] + 1; 
 //通过给d[u]加1来设置v和w之间的距离
 
 pred[w] = u; //发现顶点u的邻点w时，则设置w的前溯点值为u
 queue.enqueue(w); 
 } 
 
 } 
 color[u] = 'black'; 
 } 
 return { //返回了一个包含d和pred的对象 
 distances: d, 
 predecessors: pred 
 }; 
};

深度优先搜索，将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点被访问了，接着原路回退并探索下一条路径（它是先深度后广度地访问顶点）

访问顶点v

标注v为被发现的（灰色）。
对于v的所有未访问的邻点w，访问顶点w，标注v为已被探索的（黑色）。

示例：

// 实现一下深度优先算法
this.dfs = function(callback){ 
 var color = initializeColor(); //创建颜色数组
 
 for (var i=0; i<vertices.length; i++){ 
 //用值white为图中的每个顶点对其做初始化 
 if (color[vertices[i]] === 'white'){ 
 //调用私有的递归函数dfsVisit，传递的参数为顶点、颜色数组以及回调函数 
 dfsVisit(vertices[i], color, callback);
 } 
 } 
}; 

var dfsVisit = function(u, color, callback){ 
 color[u] = 'grey'; //标注其为被发现的
 
 if (callback) { //则执行该函数输出已访问过的顶点
 callback(u); 
 } 
 var neighbors = adjList.get(u); //取得包含顶点u所有邻点的列表
 for (var i=0; i<neighbors.length; i++){ 
 //对于顶点u的每一个未被访问过 的邻点w
 var w = neighbors[i];  
 if (color[w] === 'white'){   
 dfsVisit(w, color, callback); //将调用dfsVisit函数，传递w和其他参数
 // 添加顶点w入栈
 } 
 } 
 color[u] = 'black'; //在该顶点和邻点按深度访问之后，我们回退
 // 该顶点已被完全探索，并将其标注为black
};

探索深度优先算法

顶点u的发现时间d[u]；
当顶点u被标注为黑色时，u的完成探索时间f[u]；
顶点u的前溯点p[u]

最短路径算法

Dijkstra 算法，是一种计算从单个源到所有其他源的最短路径的贪心算法

题图：

image.png

示例：

// 看Dijkstra算法
this.dijkstra = function(src) { 
 var dist = [], visited = [], 
 
 length = this.graph.length; 
 
 for (var i = 0; i < length; i++) { //把所有的距离（dist）初始化为无限大
 dist[i] = INF; 
 visited[i] = false; 
 // 将visited[]初始化为false
 } 
 
 dist[src] = 0; //把源顶点到自己的距离设为0
 
 for (var i = 0; i < length-1; i++) { //要找出到其余顶点的最短路径
 
 var u = minDistance(dist, visited); //需要从尚未处理的顶点中选出距离最近的顶点
 
 visited[u] = true; //选出的顶点标为visited，以免重复计算
 
 for (var v = 0; v < length; v++) { 
 if (!visited[v] && 
 this.graph[u][v] != 0 && dist[u] != INF && 
 dist[u] + this.graph[u][v] < dist[v]) { 
 //如果找到更短的路径，则更新最短路径的值
 
 dist[v] = dist[u] + this.graph[u][v]; 
 } 
 } 
 } 
 return dist; //处理完所有顶点后，返回从源顶点（src）到图中其他顶点最短路径的结果
};

// 搜索dist数组中的最小值，返回它在数组中的索引
var minDistance = function(dist, visited) { 
 var min = INF, minIndex = -1; 
 for (var v = 0; v < dist.length; v++) { 
 if (visited[v] == false && dist[v] <= min) { 
 min = dist[v]; 
 minIndex = v; 
 } 
 } 
 return minIndex; 
};

Floyd-Warshall算法是一种计算图中所有最短路径的动态规划算法

// 找出从所有源到所有顶点的最短路径

this.floydWarshall = function() { 
 var dist = [], 
 length = this.graph.length, 
 i, j, k; 
 
 for (i = 0; i < length; i++) { 
 //把dist数组初始化为每个顶点之间的权值，
 //因为i到j可能的最短距离就是这些顶点间的权值 
 
 dist[i] = []; 
 for (j = 0; j < length; j++) { 
 dist[i][j] = this.graph[i][j]; 
 } 
 } 
 for (k = 0; k < length; k++) { //通过k，得到i途径顶点0至k，到达j的最短路径
 for (i = 0; i < length; i++) { 
 for (j = 0; j < length; j++) { 
 if (dist[i][k] + dist[k][j] < dist[i][j]) { //核心
 //判断i经过顶点k到达j的路径是否比已有的最短路径更短 
 dist[i][j] = dist[i][k] + dist[k][j]; //如果是更短的路径，则更新最短路径的值
 } 
 } 
 } 
 } 
 return dist; 
};

最小生成树（要在n个岛屿之间建造桥梁，想用最低的成本实现所有岛屿相互连通）

最小生成树的算法：Prim算法和Kruskal算法

104. 二叉树的最大深度

一、题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

image.png

二、思路分析

递归（树是一种递归的数据结构）

二叉数的遍历主要有前中后遍历和层次遍历。前中后属于 DFS，层次遍历属于 BFS

DFS 都可以使用栈来简化操作，并且其实树本身是一种递归的数据结构，因此递归和栈对于 DFS 来说是两个关键点

队列
队列中用 Null(一个特殊元素)来划分每层，或者在对每层进行迭代之前保存当前队列元素的个数
树的基本操作- 遍历 - 层次遍历（BFS）
标签：DFS
找出终止条件：当前节点为空
找出返回值：节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
某层的执行过程：在返回值部分基本已经描述清楚
时间复杂度：O(n)O(n)

image.png

image.png

image.png

image.png

三、答案代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
 
var maxDepth = function (root) {
  if (!root) return 0;
  if (!root.left && !root.right) return 1;

  // 层次遍历 BFS
  let cur = root;
  const queue = [root, null];
  let depth = 1;

  while ((cur = queue.shift()) !== undefined) {
    if (cur === null) {
      // 注意： 不处理会无限循环，进而堆栈溢出
      if (queue.length === 0) return depth;
      depth++;
      queue.push(null);
      continue;
    }
    const l = cur.left;
    const r = cur.right;

    if (l) queue.push(l);
    if (r) queue.push(r);
  }

  return depth;

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) {
        return 0;
    } else {
        const left = maxDepth(root.left);
        const right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
};

四、总结