七十七、 二叉樹的層次遍歷和最大深度

「@Author：Runsen」

在講解二叉樹的時候，提到二叉樹的遍歷除了前中后序遍歷，還有層次遍歷。

前中后序這三種遍歷方法以及可以通過遞歸的方式實現(xiàn)了，那么今天就來講講層次遍歷吧!

LeetCode 第 102題：二叉樹的層次遍歷

給你一個二叉樹，請你返回其按 層序遍歷 得到的節(jié)點值。（即逐層地，從左到右訪問所有節(jié)點）。

示例：?
二叉樹：[3,9,20,null,null,15,7],?
#?????3
#???/?\
#??9??20
#????/??\
#???15???7
返回其層次遍歷結(jié)果：?
[
?[3],
?[9,20],
?[15,7]
]

對于這道二叉樹題目，我們要遍歷每一層的每一個節(jié)點，可以考慮分別用BFS（廣度優(yōu)先搜索）和DFS（深度優(yōu)先搜索）來解決，下面先簡單介紹BFS，后續(xù)文章繼續(xù)深入。

有兩種通用的遍歷樹的策略：

深度優(yōu)先搜索算法（英語：Depth-First-Search，簡稱DFS）是一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當(dāng)節(jié)點的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點的那條邊的起始節(jié)點。

深度優(yōu)先搜索策略又可以根據(jù)根節(jié)點、左孩子和右孩子的相對順序被細(xì)分為先序遍歷，中序遍歷和后序遍歷。

寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索 英語：Breadth-First Search, 簡稱BFS )

我們按照高度順序一層一層的訪問整棵樹，高層次的節(jié)點將會比低層次的節(jié)點先被訪問到，最短路徑問題常用此算法。

本題就是用廣度優(yōu)先搜索，對二叉樹按照層進行搜索，搜索邏輯如下圖所示：

根據(jù)我們熟悉的BFS搜索方法，二叉樹的層次遍歷，關(guān)鍵要用到隊列，父結(jié)點出，就要判斷子結(jié)點是否為空，非空則馬上進入隊列,類似廣度優(yōu)先queue隊列。

把每個沒有搜索到的點依次放入隊列，然后再彈出隊列的頭部元素作為當(dāng)前遍歷節(jié)點，并進行記錄。接下來對此節(jié)點的所有相鄰節(jié)點進行搜索，將所有有效且未被訪問過的節(jié)點壓入隊列中。

#?Definition?for?a?binary?tree?node.
#?class?TreeNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.left?=?None
#?????????self.right?=?None
from?collections?import?deque

class?Solution(object):
????def?levelOrder(self,?root):
????????res?=?[]
????????if?root?is?None:
????????????return?res
????????q?=?deque([root])
????????res.append([root.val])
????????while?q:
????????????size?=?len(q)
????????????level?=?[]
????????????for?i?in?range(size):
????????????????node?=?q.popleft()
????????????????if?node.left?!=?None:
????????????????????q.append(node.left)
????????????????????level.append(node.left.val)
????????????????if?node.right?!=?None:
????????????????????q.append(node.right)
????????????????????level.append(node.right.val)
????????????if?level:
????????????????res.append(level)
????????return?res

LeetCode 第 107題：二叉樹的層次遍歷 II

給定一個二叉樹，返回其節(jié)點值自底向上的層次遍歷。（即按從葉子節(jié)點所在層到根節(jié)點所在的層，逐層從左向右遍歷）

#給定二叉樹?[3,9,20,null,null,15,7],?
#?????3
#???/?\
#??9??20
#????/??\
#???15???7
#?返回其自底向上的層次遍歷為：?
#?[
#??[15,7],
#??[9,20],
#??[3]
#]
#?Related?Topics?樹?廣度優(yōu)先搜索

和LeetCode 第 102題：二叉樹的層次遍歷完全一樣，就是最后的結(jié)果改為return res[::-1]

class?Solution:
????def?levelOrderBottom(self,?root:?TreeNode)?->?List[List[int]]:
????????res?=?[]
????????if?root?is?None:
????????????return?res
????????q?=?deque([root])
????????res.append([root.val])
????????while?q:
????????????size?=?len(q)
????????????level?=?[]
????????????for?i?in?range(size):
????????????????node?=?q.popleft()
????????????????if?node.left?!=?None:
????????????????????q.append(node.left)
????????????????????level.append(node.left.val)
????????????????if?node.right?!=?None:
????????????????????q.append(node.right)
????????????????????level.append(node.right.val)
????????????if?level:
????????????????res.append(level)
????????return?res[::-1]

LeetCode 第 104題：二叉樹的最大深度

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

#?二叉樹的深度為根節(jié)點到最遠(yuǎn)葉子節(jié)點的最長路徑上的節(jié)點數(shù)。?
#?說明:?葉子節(jié)點是指沒有子節(jié)點的節(jié)點。?
#?示例：?
#給定二叉樹?[3,9,20,null,null,15,7]，?
#?????3
#???/?\
#??9??20
#????/??\
#???15???7?
#?返回它的最大深度 3 。?
#?Related?Topics?樹?深度優(yōu)先搜索

看到該題目，首先想到的是使用遞歸來實現(xiàn)，遞歸的基本條件是訪問到根節(jié)點（左右子樹為空）；遞歸條件是訪問左子樹或右子樹；中間處理邏輯是將子樹深度+1，即為最終深度。

#?class?TreeNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.left?=?None
#?????????self.right?=?None

class?Solution:
?#?簡化的遞歸
?def?maxDepth(self,?root:?TreeNode)?->?int:
????????if?not?root:
????????????return?0
????????return?max(self.maxDepth(root.left),?self.maxDepth(root.right))+1
?def?maxDepth(self,?root:?TreeNode)?->?int:??
??if?not?root:?return?0?
??#?分別得到左右子樹的最大深度
??left?=?self.maxDepth(root.left)????
??right?=?self.maxDepth(root.right)????
??return?max(left,?right)?+1

LeetCode 第 110題：平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

#?本題中，一棵高度平衡二叉樹定義為：?
#?一個二叉樹每個節(jié)點?的左右兩個子樹的高度差的絕對值不超過1。?
#?示例?1:?
#?給定二叉樹?[3,9,20,null,null,15,7]?
#?????3
#???/?\
#??9??20
#????/??\
#???15???7?
#?返回 true 。?
#示例?2:?
#?給定二叉樹?[1,2,2,3,3,null,null,4,4]?
#
#????????1
#??????/?\
#?????2???2
#????/?\
#???3???3
#??/?\
#?4???4
#?返回 false 。?
#?Related?Topics?樹?深度優(yōu)先搜索

定義一個獲取當(dāng)前節(jié)點高度的方法, 可以參考上面：求二叉樹的最大深度

左右兩個子樹的高度差的絕對值超過1，則為false

如果當(dāng)前節(jié)點的左右子樹滿足高度差的絕對值不超過1，則需要繼續(xù)判斷其左右子樹分別是否是平衡二叉樹。

對于每個節(jié)點，左子樹和右子樹都是平衡樹，并且得到左子樹和右子樹的高度，只要高度差小于1，則為true。

#?Definition?for?a?binary?tree?node.
#?class?TreeNode(object):
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.left?=?None
#?????????self.right?=?None

class?Solution:
????def?isBalanced(self,?root:?TreeNode)?->?bool:
????????if?not?root:?return?True
????????return?abs(self.depth(root.left)?-?self.depth(root.right))?<=?1?and?\
????????????self.isBalanced(root.left)?and?self.isBalanced(root.right)

????def?depth(self,?root):
????????if?not?root:?return?0
????????return?max(self.depth(root.left),?self.depth(root.right))?+?

但是時間復(fù)雜度卻是，可以采用DFS（深度優(yōu)先搜索）

• 對二叉樹做深度優(yōu)先遍歷DFS，遞歸過程中：

• 終止條件：當(dāng)DFS越過葉子節(jié)點時，返回高度0；

• 返回值：從底至頂，返回以每個節(jié)點root為根節(jié)點的子樹最大高度(左右子樹中最大的高度值加1 max(left,right) + 1)；

• 當(dāng)我們發(fā)現(xiàn)有一例 左/右子樹高度差 ＞ 1 的情況時，代表此樹不是平衡樹，返回-1；

• 當(dāng)發(fā)現(xiàn)不是平衡樹時，后面的高度計算都沒有意義了，因此一路返回-1，避免后續(xù)多余計算。

最差情況是對樹做一遍完整DFS，時間復(fù)雜度為 O(N)。

class?Solution:
????def?isBalanced(self,?root:?TreeNode)?->?bool:
????????return?self.depth(root)?!=?-1

????def?depth(self,?root):
????????if?not?root:?return?0
????????left?=?self.depth(root.left)
????????if?left?==?-1:?return?-1
????????right?=?self.depth(root.right)
????????if?right?==?-1:?return?-1
????????return?max(left,?right)?+?1?if?abs(left?-?right)?2?else?-1

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

?

Reference