二叉樹的層序遍歷，就是圖論中的廣度優先搜索在二叉樹中的應用，需要借助隊列來實現（此時又發現隊列的一個應用了）。

102.二叉樹的層序遍歷

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:result = []if not root:return resultque = deque([root])while que:size = len(que)r = []for _ in range(size):cur =que.popleft()r.append(cur.val)if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)result.append(r)return result

107.二叉樹的層次遍歷II

層次遍歷后result反轉即可

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:result = []if not root:return resultque =deque([root])while que:size = len(que)r = []for _ in range(size):cur =que.popleft()r.append(cur.val)if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)result.append(r)return result[::-1]

199.二叉樹的右視圖

層序遍歷的時候，判斷是否遍歷到單層的最后面的元素，如果是，就放進result數組中，隨后返回result就可以了。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def rightSideView(self, root: TreeNode) -> List[int]:r = []if not root:return rque = deque([root])while que:size = len(que)for i in range(size):cur = que.popleft()# 說明是本層的最后一個元素 加入if i == size-1:r.append(cur.val)if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)return r

637.二叉樹的層平均值

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:r = []if not root:return rque = deque([root])while que:# 要先記下que的長度 否則移動過程長度會變化size = len(que)sum = 0ave = 0for _ in range(size):cur = que.popleft()sum += cur.valif cur.left:que.append(cur.left)if cur.right:que.append(cur.right)ave = sum/sizer.append(ave)return r

429.N叉樹的層序遍歷

""" # Definition for a Node. class Node:def __init__(self, val=None, children=None):self.val = valself.children = children """class Solution:def levelOrder(self, root: 'Node') -> List[List[int]]:result = []if not root:return resultque = deque([root])while que:r = []size = len(que)for _ in range(size):cur = que.popleft()r.append(cur.val)# 像二叉樹模板一樣 隊列中添加孩子結點if cur.children:que.extend(cur.children)result.append(r)return result

515.在每個樹行中找最大值

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def largestValues(self, root: Optional[TreeNode]) -> List[int]:result = []if not root:return resultque = deque([root])while que:r = []size = len(que)for _ in range(size):cur = que.popleft()r.append(cur.val)if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)result.append(max(r))return result

116.填充每個節點的下一個右側節點指針

本題依然是層序遍歷，只不過在單層遍歷的時候記錄一下本層的頭部節點，然后在遍歷的時候讓前一個節點指向本節點就可以了。
總結：讓當前結點（已經pop出來了）的next指向下一個結點，即隊列里的第0個

""" # Definition for a Node. class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next """class Solution:def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':if not root:return rootque = deque([root])while que:r = []size = len(que)for i in range(size):cur = que.popleft()if cur.left:que.append(cur.left)if cur.right:aque.append(cur.right)# 已經到最后一個結點 next已經默認設置成Noneif i == size-1:break# 當前結點(已經pop出來了)的next指向他的下一個結點(隊列的第0元素)cur.next = que[0]return root

117.填充每個節點的下一個右側節點指針II

思路：

這道題目說是二叉樹，但116題目說是完整二叉樹，其實沒有任何差別，一樣的代碼一樣的邏輯一樣的味道

""" # Definition for a Node. class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next """class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return rootque = deque([root])while que:r = []size = len(que)for i in range(size):cur = que.popleft()if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)# 已經到最后一個結點 next已經默認設置成Noneif i == size-1:break# 當前結點(已經pop出來了)的next指向他的下一個結點(隊列的第0元素)cur.next = que[0]return root

104.二叉樹的最大深度

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0que = deque([root])k = 0 # 記錄遍歷的層數 while que:r = []size = len(que)for i in range(size):cur = que.popleft()if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)k+=1return k

111.二叉樹的最小深度

相對于 104.二叉樹的最大深度 ，本題還也可以使用層序遍歷的方式來解決，思路是一樣的。

需要注意的是，只有當左右孩子都為空的時候，才說明遍歷的最低點了。如果其中一個孩子為空則不是最低點

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0que = deque([root])k = 0 # 記錄層數while que:size = len(que)k += 1 # 開始進入新的一層for i in range(size):cur = que.popleft()if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)# 左右孩子都空 則返回kif cur.left == None and cur.right == None:return k return 0 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0# 根節點深度1que = deque([(root,1)])while que:size = len(que)for i in range(size):cur,k = que.popleft()# 假設是根節點 左右孩子都空 則返回kif cur.left == None and cur.right == None:return k # 因為在一個for循環內 有左還右孩子 層數都加1 if cur.left:que.append((cur.left,k+1))if cur.right:que.append((cur.right,k+1))return 0

總結

以上是生活随笔為你收集整理的二叉树-层次遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。