淺析二叉樹(shù)的層次遍歷和最大深度
在講解二叉樹(shù)的時(shí)候，提到二叉樹(shù)的遍歷除了前中后序遍歷，還有層次遍歷。
前中后序這三種遍歷方法以及可以通過(guò)遞歸的方式實(shí)現(xiàn)了，那么今天就來(lái)講講層次遍歷吧!
LeetCode 第 102題：二叉樹(shù)的層次遍歷
給你一個(gè)二叉樹(shù)，請(qǐng)你返回其按 層序遍歷 得到的節(jié)點(diǎn)值。(即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn))。
- 示例：
- 二叉樹(shù)：[3,9,20,null,null,15,7],
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- 返回其層次遍歷結(jié)果：
- [
- [3],
- [9,20],
- [15,7]
- ]
對(duì)于這道二叉樹(shù)題目，我們要遍歷每一層的每一個(gè)節(jié)點(diǎn)，可以考慮分別用BFS(廣度優(yōu)先搜索)和DFS(深度優(yōu)先搜索)來(lái)解決，下面先簡(jiǎn)單介紹BFS，后續(xù)文章繼續(xù)深入。
有兩種通用的遍歷樹(shù)的策略：
深度優(yōu)先搜索算法(英語(yǔ)：Depth-First-Search，簡(jiǎn)稱DFS)是一種用于遍歷或搜索樹(shù)或圖的算法。沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。當(dāng)節(jié)點(diǎn)的所在邊都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)的那條邊的起始節(jié)點(diǎn)。
深度優(yōu)先搜索策略又可以根據(jù)根節(jié)點(diǎn)、左孩子和右孩子的相對(duì)順序被細(xì)分為先序遍歷，中序遍歷和后序遍歷。
寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索 英語(yǔ)：Breadth-First Search, 簡(jiǎn)稱BFS )
我們按照高度順序一層一層的訪問(wèn)整棵樹(shù)，高層次的節(jié)點(diǎn)將會(huì)比低層次的節(jié)點(diǎn)先被訪問(wèn)到，最短路徑問(wèn)題常用此算法。
本題就是用廣度優(yōu)先搜索，對(duì)二叉樹(shù)按照層進(jìn)行搜索，搜索邏輯如下圖所示：
根據(jù)我們熟悉的BFS搜索方法，二叉樹(shù)的層次遍歷，關(guān)鍵要用到隊(duì)列，父結(jié)點(diǎn)出，就要判斷子結(jié)點(diǎn)是否為空，非空則馬上進(jìn)入隊(duì)列,類似廣度優(yōu)先queue隊(duì)列。
把每個(gè)沒(méi)有搜索到的點(diǎn)依次放入隊(duì)列，然后再?gòu)棾鲫?duì)列的頭部元素作為當(dāng)前遍歷節(jié)點(diǎn)，并進(jìn)行記錄。接下來(lái)對(duì)此節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)進(jìn)行搜索，將所有有效且未被訪問(wèn)過(guò)的節(jié)點(diǎn)壓入隊(duì)列中。
- # 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題：二叉樹(shù)的層次遍歷II
給定一個(gè)二叉樹(shù)，返回其節(jié)點(diǎn)值自底向上的層次遍歷。(即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層，逐層從左向右遍歷)
- #給定二叉樹(shù) [3,9,20,null,null,15,7],
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- # 返回其自底向上的層次遍歷為：
- # [
- # [15,7],
- # [9,20],
- # [3]
- #]
- # Related Topics 樹(shù) 廣度優(yōu)先搜索
和LeetCode 第 102題：二叉樹(shù)的層次遍歷完全一樣，就是最后的結(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題：二叉樹(shù)的最大深度
給定一個(gè)二叉樹(shù)，找出其最大深度。
- # 二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
- # 說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
- # 示例：
- #給定二叉樹(shù) [3,9,20,null,null,15,7]，
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- # 返回它的最大深度 3 。
- # Related Topics 樹(shù) 深度優(yōu)先搜索
看到該題目，首先想到的是使用遞歸來(lái)實(shí)現(xiàn)，遞歸的基本條件是訪問(wèn)到根節(jié)點(diǎn)(左右子樹(shù)為空);遞歸條件是訪問(wèn)左子樹(shù)或右子樹(shù);中間處理邏輯是將子樹(shù)深度+1，即為最終深度。
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- # 簡(jiǎn)化的遞歸
- 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
- # 分別得到左右子樹(shù)的最大深度
- left = self.maxDepth(root.left)
- right = self.maxDepth(root.right)
- return max(left, right) +1
LeetCode 第 110題：平衡二叉樹(shù)
給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。
- # 本題中，一棵高度平衡二叉樹(shù)定義為：
- # 一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。
- # 示例 1:
- # 給定二叉樹(shù) [3,9,20,null,null,15,7]
- # 3
- # / \
- # 9 20
- # / \
- # 15 7
- # 返回 true 。
- #示例 2:
- # 給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]
- #
- # 1
- # / \
- # 2 2
- # / \
- # 3 3
- # / \
- # 4 4
- # 返回 false 。
- # Related Topics 樹(shù) 深度優(yōu)先搜索
定義一個(gè)獲取當(dāng)前節(jié)點(diǎn)高度的方法, 可以參考上面：求二叉樹(shù)的最大深度
左右兩個(gè)子樹(shù)的高度差的絕對(duì)值超過(guò)1，則為false
如果當(dāng)前節(jié)點(diǎn)的左右子樹(shù)滿足高度差的絕對(duì)值不超過(guò)1，則需要繼續(xù)判斷其左右子樹(shù)分別是否是平衡二叉樹(shù)。
對(duì)于每個(gè)節(jié)點(diǎn)，左子樹(shù)和右子樹(shù)都是平衡樹(shù)，并且得到左子樹(shù)和右子樹(shù)的高度，只要高度差小于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)) +
但是時(shí)間復(fù)雜度卻是，可以采用DFS(深度優(yōu)先搜索)
- 對(duì)二叉樹(shù)做深度優(yōu)先遍歷DFS，遞歸過(guò)程中：
- 終止條件：當(dāng)DFS越過(guò)葉子節(jié)點(diǎn)時(shí)，返回高度0;
- 返回值：從底至頂，返回以每個(gè)節(jié)點(diǎn)root為根節(jié)點(diǎn)的子樹(shù)最大高度(左右子樹(shù)中最大的高度值加1 max(left,right) + 1);
- 當(dāng)我們發(fā)現(xiàn)有一例 左/右子樹(shù)高度差 > 1 的情況時(shí)，代表此樹(shù)不是平衡樹(shù)，返回-1;
- 當(dāng)發(fā)現(xiàn)不是平衡樹(shù)時(shí)，后面的高度計(jì)算都沒(méi)有意義了，因此一路返回-1，避免后續(xù)多余計(jì)算。
最差情況是對(duì)樹(shù)做一遍完整DFS，時(shí)間復(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 https://github.com/MaoliRUNsen/runsenlearnpy100更多的文章
