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

Github來源：力扣 (LeetCode)｜刷題打卡 | 求星星 ? | 給個??關(guān)注，??點贊，??鼓勵一下作者

[已開啟]任務(wù)一：刷題打卡 * 10 篇

哪吒人生信條：如果你所學的東西 處于喜歡 才會有強大的動力支撐。

每天學習編程，讓你離夢想更新一步，感謝不負每一份熱愛編程的程序員，不論知識點多么奇葩，和我一起，讓那一顆四處流蕩的心定下來，一直走下去，加油，2021加油！歡迎關(guān)注加我vx:xiaoda0423，歡迎點贊、收藏和評論

時間：3 月 1 日 ～ 3 月 13 日

• 力扣 (LeetCode)-兩數(shù)之和,有效的括號,兩數(shù)相加｜刷題打卡-3月1日
• 力扣 (LeetCode)-合并兩個有序鏈表,刪除排序數(shù)組中的重復項,JavaScript筆記｜刷題打卡-3月2日
• 力扣 (LeetCode)-最大子序和,JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（數(shù)組）｜刷題打卡-3月3日
• 針對CSS說一說｜技術(shù)點評-3月4日
• 力扣 (LeetCode)-棧,括號生成 ｜刷題打卡-3月5日
• 原來也沒有那么難！Vue商城開發(fā) | 技術(shù)點評-3月6日
• 力扣 (LeetCode)-加一，隊列 ｜刷題打卡-3月7日
• JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表 | 技術(shù)點評-3月8日
• JavaScript的數(shù)據(jù)結(jié)構(gòu)-集合 ｜技術(shù)點評-3月9號
• 力扣 (LeetCode)-合并兩個有序數(shù)組,字典,散列表｜刷題打卡-3月10號
• 力扣 (LeetCode)-對稱二叉樹,樹｜刷題打卡

前言

如果這篇文章有幫助到你，給個??關(guān)注，??點贊，??鼓勵一下作者，接收好挑戰(zhàn)了嗎？文章公眾號首發(fā)，關(guān)注 程序員哆啦A夢 第一時間獲取最新的文章

??筆芯??~

棧，隊列，鏈表，集合，字典和散列表，樹

圖

• 圖是網(wǎng)絡(luò)結(jié)構(gòu)的抽象模型。
• 圖是一組由邊連接的節(jié)點（或頂點）
• 一個圖G=(V,E)由V:一組頂點，E:一組邊，連接V中的頂點
• 由一條邊連接在一起的頂點稱為相鄰頂點
• 一個頂點的度是其相鄰頂點的數(shù)量
• 路徑是頂點v1, v2,…,vk的一個連續(xù)序列，其中vi和vi+1是相鄰的
• 簡單路徑要求不包含重復的頂點（環(huán)也是一個簡單路徑）
• 如果圖中不存在環(huán)，則稱圖為無環(huán)的，如果圖中每兩個頂點間都存在路徑，則該圖是連通的
• 圖可以是無向的（邊沒有方向）或是有向的（有向圖）
• 如果圖中每兩個頂點間在雙向上都存在路徑，則該圖是強連通的
• 圖還可以是未加權(quán)的或是加權(quán)的

鄰接矩陣

每個節(jié)點都和一個整數(shù)相關(guān)聯(lián)，該整數(shù)將作為數(shù)組的索引。

如果索引為i的節(jié)點和索引為j的節(jié)點相鄰，則array[i][j] === 1，否則array[i][j] === 0

鄰接表

• 鄰接表的動態(tài)數(shù)據(jù)結(jié)構(gòu)來表示圖
• 鄰接表由圖中每個頂點的相鄰頂點列表所組成

關(guān)聯(lián)矩陣

• 使用關(guān)聯(lián)矩陣來表示圖
• 在關(guān)聯(lián)矩陣中，矩陣的行表示頂點，列表示邊
• 關(guān)聯(lián)矩陣用于邊的數(shù)量比頂點多的情況下，以節(jié)省空間和內(nèi)存

創(chuàng)建Graph類

function Graph(){
// 使用一個數(shù)組來存儲圖中所有頂點的名字
 var vertices = [];
 // 一個字典來存儲鄰接表
 var adjList = new Dictionary();
}

• 字典將會使用頂點的名字作為鍵，鄰接頂點列表作為值

1. 一個用來向圖中添加一個新的頂點
2. 一個方法用來添加頂點之間的邊

this.addVertex = function(v){ 
// 將該頂點添加到頂點列表中
 vertices.push(v); //法接受頂點v作為參數(shù)
 adjList.set(v, []); 
 //在鄰接表中，設(shè)置頂點v作為鍵對應(yīng)的字典值為一個空數(shù)組 
};

this.addEdge = function(v, w){ 
// 接受兩個頂點作為參數(shù)
 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']; 
//創(chuàng)建了一個數(shù)組，包含所有我們想添加到圖中的頂點 

for (var i=0; i<myVertices.length; i++){ 
//遍歷vertices數(shù)組并將其中的值逐一添加到我們的圖中

 graph.addVertex(myVertices[i]); 
} 

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

實現(xiàn)一下Graph類的toString方法

this.toString = function(){ 
 var s = ''; // 構(gòu)建了一個字符串
 
 for (var i=0; i<vertices.length; i++){ //迭代vertices數(shù)組列表
 
 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; 
};

圖的遍歷

• 廣度優(yōu)先搜索（Breadth-First Search，BFS）
• 深度優(yōu)先搜索（Depth-First Search，DFS）

廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法，只有一點不同，那就是待訪問頂點列表的數(shù)據(jù)結(jié)構(gòu)。

圖遍歷的思想方法（指出第一個被訪問的頂點）

必須追蹤每個第一次訪問的節(jié)點，并且追蹤有哪些節(jié)點還沒有被完全探索

深度優(yōu)先搜索算法，數(shù)據(jù)結(jié)構(gòu)是棧，通過將頂點存入棧中，頂點是沿著路徑被探索的，存在新的相鄰頂點就去訪問

廣度優(yōu)先搜索算法，數(shù)據(jù)結(jié)構(gòu)是隊列，通過將頂點存入隊列中，最先入隊列的頂點先被探索

• 白色，表示該頂點還沒有被訪問
• 灰色，表示該頂點被訪問過，但并未被探索過
• 黑色，表示該頂點被訪問過且被完全探索過

務(wù)必訪問每個頂點最多兩次

廣度優(yōu)先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪 問圖的一層（就是先寬后深地訪問頂點）

示例：

// 執(zhí)行此初始化操作
var initializeColor = function(){ 
// 都需要標注被訪問過的頂點
 var color = []; 
 // 使用一個輔助數(shù)組color
 
 for (var i=0; i<vertices.length; i++){ 
 color[vertices[i]] = 'white'; //開始執(zhí)行時，所有的頂點顏色都是白色
 } 
 return color; 
};

// 接受一個頂點作為算法的起始點 接受一個回調(diào)
this.bfs = function(v, callback){ 
 var color = initializeColor(), 
 //用initializeColor函數(shù)來將color數(shù)組初始化為white 
 
 queue = new Queue(); //還需要聲明和創(chuàng)建一個Queue實例
 
 queue.enqueue(v); //將會存儲待訪問和待探索的頂點
 
 while (!queue.isEmpty()){ //如果隊列非空 
 var u = queue.dequeue(), //將通過出隊列 
 // 操作從隊列中移除一個頂點
 neighbors = adjList.get(u); 
 //取得一個包含其所有鄰點的鄰接表
 
 color[u] = 'grey'; //該頂點將被標注為grey
 // 表示我們發(fā)現(xiàn)了它，但未完成對其搜索
 
 for (var i=0; i<neighbors.length; i++){ //每個鄰點 
 var w = neighbors[i]; //取得其值
 
 if (color[w] === 'white'){ 
 //如果它還未被訪問過
 color[w] = 'grey'; //則將其標注為我們已經(jīng)發(fā)現(xiàn)了它 
 queue.enqueue(w); //將這個頂點加入隊列中 
 } 
 } 
 color[u] = 'black'; 
 // 當完成探索該頂點和其相鄰頂點后，我們將該頂點標注為已探索過的 
 if (callback) { //如果我們傳遞了回調(diào)函數(shù)
 callback(u); // 會用到它
 } 
 } 
};

• 使用BFS尋找最短路徑

題：給定一個圖G和源頂點v，找出對每個頂點u，u和v之間最短路徑的距離（以邊的數(shù)量計）。

思路：對于給定頂點v，廣度優(yōu)先算法會訪問所有與其距離為1的頂點，接著是距離為2的頂點，以此類推。

• 從v到u的距離d[u]；
• 前溯點pred[u]，用來推導出從v到其他每個頂點u的最短路徑。

this.BFS = function(v){ 
 var color = initializeColor(), 
 queue = new Queue(), 
 d = [], //聲明數(shù)組d
 // 表示距離
 
 pred = []; //及pred數(shù)組來表示前溯點
 
 queue.enqueue(v); 
 for (var i=0; i<vertices.length; i++){
 d[vertices[i]] = 0; //圖中的每一個頂點，用0來初始化數(shù)組d 
 pred[vertices[i]] = null; //用null來初始化數(shù)組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來設(shè)置v和w之間的距離
 
 pred[w] = u; //發(fā)現(xiàn)頂點u的鄰點w時，則設(shè)置w的前溯點值為u
 queue.enqueue(w); 
 } 
 
 } 
 color[u] = 'black'; 
 } 
 return { //返回了一個包含d和pred的對象 
 distances: d, 
 predecessors: pred 
 }; 
};

深度優(yōu)先搜索，將會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最后一個頂 點被訪問了，接著原路回退并探索下一條路徑（它是先深度后廣度地訪問頂點）

• 訪問頂點v

1. 標注v為被發(fā)現(xiàn)的（灰色）。
2. 對于v的所有未訪問的鄰點w，訪問頂點w，標注v為已被探索的（黑色）。

示例：

// 實現(xiàn)一下深度優(yōu)先算法
this.dfs = function(callback){ 
 var color = initializeColor(); //創(chuàng)建顏色數(shù)組
 
 for (var i=0; i<vertices.length; i++){ 
 //用值white為圖中的每個頂點對其做初始化 
 if (color[vertices[i]] === 'white'){ 
 //調(diào)用私有的遞歸函數(shù)dfsVisit，傳遞的參數(shù)為頂點、顏色數(shù)組以及回調(diào)函數(shù) 
 dfsVisit(vertices[i], color, callback);
 } 
 } 
}; 

var dfsVisit = function(u, color, callback){ 
 color[u] = 'grey'; //標注其為被發(fā)現(xiàn)的
 
 if (callback) { //則執(zhí)行該函數(shù)輸出已訪問過的頂點
 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); //將調(diào)用dfsVisit函數(shù)，傳遞w和其他參數(shù)
 // 添加頂點w入棧
 } 
 } 
 color[u] = 'black'; //在該頂點和鄰點按深度訪問之后，我們回退
 // 該頂點已被完全探索，并將其標注為black
};

• 探索深度優(yōu)先算法

1. 頂點u的發(fā)現(xiàn)時間d[u]；
2. 當頂點u被標注為黑色時，u的完成探索時間f[u]；
3. 頂點u的前溯點p[u]

最短路徑算法

• Dijkstra 算法，是一種計算從單個源到所有其他源的最短路徑的貪心算法

題圖：

示例：

// 看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; //把源頂點到自己的距離設(shè)為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）到圖中其他頂點最短路徑的結(jié)果
};

// 搜索dist數(shù)組中的最小值，返回它在數(shù)組中的索引
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算法是一種計算圖中所有最短路徑的動態(tài)規(guī)劃算法

// 找出從所有源到所有頂點的最短路徑

this.floydWarshall = function() { 
 var dist = [], 
 length = this.graph.length, 
 i, j, k; 
 
 for (i = 0; i < length; i++) { 
 //把dist數(shù)組初始化為每個頂點之間的權(quán)值，
 //因為i到j(luò)可能的最短距離就是這些頂點間的權(quán)值 
 
 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經(jīng)過頂點k到達j的路徑是否比已有的最短路徑更短 
 dist[i][j] = dist[i][k] + dist[k][j]; //如果是更短的路徑，則更新最短路徑的值
 } 
 } 
 } 
 } 
 return dist; 
};

最小生成樹（要在n個島嶼之間建造橋梁，想用最低的成本實現(xiàn)所有島嶼相互連通）

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

104. 二叉樹的最大深度

一、題目描述

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。

說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

二、思路分析

• 遞歸（樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)）

二叉數(shù)的遍歷主要有前中后遍歷和層次遍歷。前中后屬于 DFS，層次遍歷屬于 BFS

DFS 都可以使用棧來簡化操作，并且其實樹本身是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，因此遞歸和棧對于 DFS 來說是兩個關(guān)鍵點

• 隊列

• 隊列中用 Null(一個特殊元素)來劃分每層，或者在對每層進行迭代之前保存當前隊列元素的個數(shù)

• 樹的基本操作- 遍歷 - 層次遍歷（BFS）

• 標簽：DFS

• 找出終止條件：當前節(jié)點為空

• 找出返回值：節(jié)點為空時說明高度為 0，所以返回 0；節(jié)點不為空時則分別求左右子樹的高度的最大值，同時加1表示當前節(jié)點的高度，返回該數(shù)值

• 某層的執(zhí)行過程：在返回值部分基本已經(jīng)描述清楚

• 時間復雜度：O(n)O(n)

三、答案代碼

/**
 * @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) {
      // 注意： 不處理會無限循環(huán)，進而堆棧溢出
      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;
    }
};

四、總結(jié)

二叉樹的最大深度，圖