二叉樹(shù)的廣度優(yōu)先搜索即從上到下、從左到右地進(jìn)行搜索，對(duì)于層序遍歷（Level Order）問(wèn)題，即依次遍歷第一層節(jié)點(diǎn)、第二層節(jié)點(diǎn)…等，基本可以秒殺。

廣度優(yōu)先搜索是通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)的，python中優(yōu)先用collections.deque，因?yàn)閐eque的 popleft() 比列表的 pop(0) 快不少。

劍指 Offer 32 - I. 從上到下打印二叉樹(shù)

import collections # leetcode里面可以去掉，下面都省略 class Solution:def levelOrder(self, root: TreeNode) -> List[int]:ans = list()if not root:return ansqueue = collections.deque()queue.append(root)while queue:node = queue.popleft()ans.append(node.val)if node.left: # 左子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.left)if node.right: # 右子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.right)return ans

從根節(jié)點(diǎn)開(kāi)始，每個(gè)節(jié)點(diǎn)入隊(duì)之后，在出隊(duì)的時(shí)候把它的左右子節(jié)點(diǎn)也入隊(duì)（如果非空），則該隊(duì)列就完成了廣度優(yōu)先搜索。

102. 二叉樹(shù)的層序遍歷 (劍指 Offer 32 - II. 從上到下打印二叉樹(shù) II)

class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:ans = list()if not root: # 判斷空樹(shù)return ansqueue = collections.deque()queue.append(root)while queue:curLevel = list()for i in range(len(queue)):node = queue.popleft()curLevel.append(node.val)if node.left: # 左子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.left)if node.right: # 右子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.right)ans.append(curLevel)return ans

需要把同一層的節(jié)點(diǎn)放到同一個(gè)數(shù)組中，方法是用一個(gè)當(dāng)前層數(shù)組 curLevel，通過(guò)循環(huán)每次把同一層的節(jié)點(diǎn)的子節(jié)點(diǎn)全部入隊(duì)，同時(shí)將這些節(jié)點(diǎn)的值記錄到curLevel 中，一層節(jié)點(diǎn)遍歷完之后將 curLevel 加入結(jié)果數(shù)組 ans 中。

103. 二叉樹(shù)的鋸齒形層序遍歷（劍指 Offer 32 - III. 從上到下打印二叉樹(shù) III）

class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:ans = list()if not root: # 判斷空樹(shù)return ansqueue = collections.deque()queue.append(root)odd = True # 奇偶層標(biāo)志while queue:curLevel = list()for i in range(len(queue)):node = queue.popleft()curLevel.append(node.val)if node.left: # 左子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.left)if node.right: # 右子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.right)if odd:ans.append(curLevel)odd = Falseelse:ans.append(curLevel[::-1])odd = Truereturn ans

按照之字形順序打印二叉樹(shù)，只需要加個(gè)奇偶層標(biāo)志即可。

1609. 奇偶樹(shù)

class Solution:def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:if not root: # 判斷空樹(shù)return anslevel = 0queue = collections.deque()queue.append(root)while queue:curLevel = []for i in range(len(queue)):node = queue.popleft()if (level % 2 == 0 and node.val % 2 == 0) or (level % 2 != 0 and node.val % 2 != 0):return Falseelse:if len(curLevel) == 0:curLevel.append(node.val)elif (level % 2 == 0 and node.val <= curLevel[-1]) or (level % 2 != 0 and node.val >= curLevel[-1]):return FalsecurLevel.append(node.val)if node.left: # 左子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.left)if node.right: # 右子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.right)level += 1return True

根據(jù)所在層數(shù)的奇偶，判斷節(jié)點(diǎn)值的奇偶以及遞增或遞減是否符合奇偶樹(shù)的要求。

107. 二叉樹(shù)的層序遍歷 II

class Solution:def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:ans = list()if not root:return ansqueue = collections.deque()queue.append(root)while queue:curLevel = list()for i in range(len(queue)):node = queue.popleft()curLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(curLevel)return ans[::-1]

唯一區(qū)別就是輸出結(jié)果時(shí)倒轉(zhuǎn)輸出。

226. 翻轉(zhuǎn)二叉樹(shù)

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:returnqueue = collections.deque()queue.append(root)while queue:for _ in range(len(queue)):node = queue.popleft()node.left, node.right = node.right, node.leftif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

層序遍歷時(shí)，交換節(jié)點(diǎn)的左右子節(jié)點(diǎn)，就完成了翻轉(zhuǎn)二叉樹(shù)，用前中后序遍歷的寫(xiě)法見(jiàn)這篇文章。

104. 二叉樹(shù)的最大深度

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0queue = collections.deque()queue.append(root)depth = 0while queue:depth += 1for _ in range(len(queue)):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth

二叉樹(shù)的最大深度，就是二叉樹(shù)的層數(shù)。

111. 二叉樹(shù)的最小深度

class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0queue = collections.deque()queue.append(root)depth = 1while queue:for i in range(len(queue)):node = queue.popleft()if not node.left and not node.right:return depthif node.left: # 左子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.left)if node.right: # 右子節(jié)點(diǎn)非空，加入隊(duì)列queue.append(node.right)depth += 1

只需要用depth記錄層數(shù)，當(dāng)遇到葉節(jié)點(diǎn)就返回depth，即為最小深度。

199. 二叉樹(shù)的右視圖

class Solution:def rightSideView(self, root: TreeNode) -> List[int]:ans = list()if not root:return ansqueue = collections.deque()queue.append(root)while queue:n = len(queue)for i in range(n):node = queue.popleft()if i == n - 1:ans.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return ans

結(jié)果需要的是每一層的最右邊的數(shù)，因此循環(huán)到最右邊的數(shù)時(shí)，才將節(jié)點(diǎn)加入結(jié)果數(shù)組 ans。

513. 找樹(shù)左下角的值

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:if not root:return 0queue = collections.deque()queue.append(root)while queue:curLevel = list()for i in range(len(queue)):node = queue.popleft()curLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return curLevel[0]

結(jié)果需要的是最底層的最左邊節(jié)點(diǎn)的值，因此用curLevel數(shù)組記錄每層的節(jié)點(diǎn)值，最后返回curLevel[0]就是最底層的最左邊節(jié)點(diǎn)的值。

1302. 層數(shù)最深葉子節(jié)點(diǎn)的和

class Solution:def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:# 題目說(shuō)了非空樹(shù)queue = collections.deque()queue.append(root)while queue:curLevel = 0for i in range(len(queue)):node = queue.popleft()curLevel += node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)return curLevel

返回最后一層的節(jié)點(diǎn)之和。

637. 二叉樹(shù)的層平均值

class Solution:def averageOfLevels(self, root: TreeNode) -> List[float]:ans = list()if not root:return ansqueue = collections.deque()queue.append(root)while queue:currLevel = list()n = len(queue)for i in range(n):node = queue.popleft()currLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(mean(currLevel))return ans

結(jié)果需要的是每一層的平均數(shù)，因此將平均數(shù)加入結(jié)果數(shù)組 ans。

515. 在每個(gè)樹(shù)行中找最大值

class Solution:def largestValues(self, root: TreeNode) -> List[int]:ans = list()if not root:return ansqueue = collections.deque()queue.append(root)while queue:currLevel = list()n = len(queue)for i in range(n):node = queue.popleft()currLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(max(currLevel))return ans

結(jié)果需要的是每一層的最大數(shù)，因此將最大數(shù)加入結(jié)果數(shù)組 ans。

1161. 最大層內(nèi)元素和

class Solution:def maxLevelSum(self, root: TreeNode) -> int:if not root:return 0queue = collections.deque()queue.append(root)MaxValue = -float('inf')ans = 1depth = 1while queue:curLevel = 0for i in range(len(queue)):node = queue.popleft()curLevel += node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)if curLevel > MaxValue:MaxValue = curLevelans = depthdepth += 1return ans

目標(biāo)是找到層值之和最大的那一層，記錄層數(shù)和最大值即可，注意 MaxValue 初始值要設(shè)成負(fù)無(wú)窮 -float(‘inf’) 。

429. N 叉樹(shù)的層序遍歷

""" # Definition for a Node. class Node:def __init__(self, val=None, children=None):self.val = valself.children = children """ import collections class Solution:def levelOrder(self, root: 'Node') -> List[List[int]]:ans = list()if not root:return ansqueue = collections.deque()queue.append(root)while queue:curLevel = list()for i in range(len(queue)):node = queue.popleft()curLevel.append(node.val)for child in node.children: # 區(qū)別if child:queue.append(child)ans.append(curLevel)return ans

N叉數(shù)是 children 列表而二叉樹(shù)是 left 和 right ，遍歷 children 即可。

116. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return rootqueue = collections.deque()queue.append(root)while queue:size = len(queue)for i in range(size):node = queue.popleft()if i < size - 1: # 必須使用 sizenode.next = queue[0]if node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

層序遍歷一次二叉樹(shù)，記錄節(jié)點(diǎn)是隊(duì)列先進(jìn)先出的，所以左邊的節(jié)點(diǎn)先出來(lái)，它的 next 就為 queue[0]，注意 len(queue) 是會(huì)變化的，所以必須使用 size 記錄一層的長(zhǎng)度。

117 . 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 II

class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return rootqueue = collections.deque()queue.append(root)while queue:size = len(queue)for i in range(size):node = queue.popleft()if i < size - 1:node.next = queue[0]if node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

不完美的二叉樹(shù)，但是和上一題一模一樣的代碼。

623. 在二叉樹(shù)中增加一行

class Solution:def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:if depth == 1:new_root = TreeNode(val = val, left = root, right = None)return new_rootqueue = collections.deque()queue.append((root, 1))while queue:for _ in range(len(queue)):node, d = queue.popleft()if d == depth - 1:old_left = node.leftold_right = node.rightnode.left = TreeNode(val = val, left = old_left, right = None)node.right = TreeNode(val = val, left = None, right = old_right)else:if node.left:queue.append((node.left, d+1))if node.right:queue.append((node.right, d+1))return root

如果在第一行增加，那就是創(chuàng)建一個(gè)新的根節(jié)點(diǎn)，然后將原根節(jié)點(diǎn)作為左子節(jié)點(diǎn)。否則的話(huà)，就在隊(duì)列中使用多一個(gè)參數(shù) d 來(lái)記錄深度，在 d - 1 層進(jìn)行增加一行的操作，先記住節(jié)點(diǎn)原來(lái)的左右子節(jié)點(diǎn) old_left 與 old_right，然后創(chuàng)建新的節(jié)點(diǎn)即可。關(guān)鍵是必須使用 for 循環(huán)，對(duì)整個(gè)第 d - 1 層都進(jìn)行同樣的操作。

662. 二叉樹(shù)最大寬度

class Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:ans = 1if not root:return 0queue = collections.deque()queue.append((root, 1))while queue:cur = []for _ in range(len(queue)):node, pos = queue.popleft()cur.append(pos)if node.left:queue.append((node.left, 2 * pos - 1))if node.right:queue.append((node.right, 2 * pos))if max(cur) - min(cur) + 1 > ans:ans = max(cur) - min(cur) + 1return ans

在隊(duì)列中使用多一個(gè)參數(shù) pos 來(lái)記錄位置，只需要記住的是，位置為 pos 的節(jié)點(diǎn)（從 1 開(kāi)始）的左子節(jié)點(diǎn)位置是 2 * pos - 1，右子節(jié)點(diǎn)的位置是 2 * pos。

958. 二叉樹(shù)的完全性檢驗(yàn)

class Solution:def isCompleteTree(self, root: TreeNode) -> bool:queue = collections.deque()queue.append((root, 1))depth = 0while queue:if len(queue) == 2**depth:for i in range(len(queue)):node, pos = queue.popleft()if node.left:queue.append((node.left, pos*2-1))if node.right:queue.append((node.right, pos*2))depth += 1else:for i in range(len(queue)):node, pos = queue.popleft()if node.left or node.right or (i+1) != pos:return Falsereturn True

與上一題類(lèi)似的，關(guān)鍵是記錄節(jié)點(diǎn)的位置（注意位置從 1 開(kāi)始）。在滿(mǎn)層中正常遍歷，一旦遇到不滿(mǎn)的層，如果其中有非葉子節(jié)點(diǎn)或者位置對(duì)不上則不是完全二叉樹(shù)。

993. 二叉樹(shù)的堂兄弟節(jié)點(diǎn)

class Solution:def isCousins(self, root: TreeNode, x: int, y: int) -> bool:# x 和 y 的深度與父節(jié)點(diǎn)x_depth, x_parent, y_depth, y_parent = None, None, None, None level = 0queue = collections.deque([(root, None)])while queue:n = len(queue)level += 1for i in range(n):node, node_parent = queue.popleft()# 每個(gè)節(jié)點(diǎn)的值都是唯一的if node.val == x:x_depth = levelx_parent = node_parentif node.val == y:y_depth = levely_parent = node_parentif node.left:queue.append((node.left, node))if node.right:queue.append((node.right, node))return x_depth == y_depth and x_parent != y_parent

由于題目中說(shuō)明每個(gè)節(jié)點(diǎn)的值都是唯一的，所以用四個(gè)變量分別表示 x 和 y 的深度與父節(jié)點(diǎn)。然后在隊(duì)列中要同時(shí)記錄節(jié)點(diǎn)和節(jié)點(diǎn)的父節(jié)點(diǎn)，如果遇到值為 x 或 y 的節(jié)點(diǎn)就記錄其深度和父節(jié)點(diǎn)，最后進(jìn)行比較即可。

總結(jié)

以上是生活随笔為你收集整理的二叉树层序遍历（广度优先搜索）基础概念与经典题目（Leetcode题解-Python语言）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。