本題是二叉樹的層序遍歷模板：每次循環(huán)將一層節(jié)點出隊，再將一層節(jié)點入隊，也是所有可用層序遍歷解二叉樹題目的模板，只需要在模板里稍加改動即可解題

from typing import List, Optional, Union
from collections import deque
'''
102. 二叉樹的層序遍歷
給你二叉樹的根節(jié)點 root ，返回其節(jié)點值的 層序遍歷 。 （即逐層地，從左到右訪問所有節(jié)點）。
示例 1:輸入：root = [3,9,20,null,null,15,7]輸出：[[3],[9,20],[15,7]]
題眼：基礎(chǔ)
思路：利用隊列實現(xiàn)
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、轉(zhuǎn)換為順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、轉(zhuǎn)換為鏈式存儲：雙指針root = tmpTree[0]parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親節(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子節(jié)點存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下個節(jié)點的左孩子parent += 1  # 更新遍歷雙親節(jié)點return rootclass Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if root == None:return []result = []que = deque()que.append(root)  # 隊列初始值while len(que) > 0:size = len(que)  # 當(dāng)前隊列長度==二叉樹一層的節(jié)點個數(shù)layer = []for _ in range(size):  # 一層遍歷node = que.popleft()  # 記錄下出隊的節(jié)點layer.append(node.val)# 和之前深度遍歷一樣：空節(jié)點不入隊，不然對None節(jié)點取值會出錯if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result.append(layer)return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.levelOrder(root))except EOFError:break

“102. 二叉樹的層序遍歷”的結(jié)果反轉(zhuǎn)/逆序即可

from typing import List, Optional, Union
from collections import deque
'''
107. 二叉樹的層序遍歷 II
給你二叉樹的根節(jié)點 root ，返回其節(jié)點值 自底向上的層序遍歷 。 （即按從葉子節(jié)點所在層到根節(jié)點所在的層，逐層從左向右遍歷）
示例 1:輸入：root = [3,9,20,null,null,15,7]輸出：[[15,7],[9,20],[3]]
題眼：自底向上的層序遍歷
思路：“102. 二叉樹的層序遍歷”的結(jié)果反轉(zhuǎn)/逆序即可
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、鏈式存儲：雙指針root = tmpTree[0]parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親節(jié)點有效if tmpTree[child] != None:  # 左孩子有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下個節(jié)點的左孩子parent += 1return rootclass Solution:def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:# 情況1、樹為空if root == None:return []# 情況2、樹不為空que = deque()que.append(root)result = []while len(que) > 0:size = len(que)  # 當(dāng)前隊列長度==二叉樹一層的節(jié)點個數(shù)layer = []for _ in range(size):  # 一層遍歷node = que.popleft()layer.append(node.val)if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result.append(layer)# 反轉(zhuǎn)result# left, right = 0, len(result) - 1# while left < right:#     result[left], result[right] = result[right], result[left]#     left += 1#     right -= 1return result[::-1]if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)print(nums)root = buildBinaryTree(nums)print(obj.levelOrderBottom(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，要訪問每個節(jié)點的N個孩子

from typing import List, Optional, Union
from collections import deque
'''
429. N 叉樹的層序遍歷
給定一個 N 叉樹，返回其節(jié)點值的層序遍歷。（即從左到右，逐層遍歷）。
樹的序列化輸入是用層序遍歷，每組子節(jié)點都由 null 值分隔（參見示例）。
示例 1:輸入：root = [1,null,3,2,4,null,5,6]輸出：[[1],[3,2,4],[5,6]]
題眼：N 叉樹的層序遍歷
思路：一般 層序遍歷的基礎(chǔ)上，要訪問每個節(jié)點的N個孩子
'''class Node:def __init__(self, val=None, children=None):self.val = valself.children = childrenclass Solution:def levelOrder(self, root: Node) -> List[List[int]]:# 情況1、樹為空if root == None:return []# 情況2、樹不為空que = deque()que.append(root)result = []while len(que) > 0:size = len(que)layer = []for _ in range(size):  # 一層遍歷node = que.popleft()layer.append(node.val)if node.children != None:for child in node.children:que.append(child)result.append(layer)return result

from typing import List, Optional, Union
from collections import deque
'''
637. 二叉樹的層平均值
給定一個非空二叉樹的根節(jié)點 root , 以數(shù)組的形式返回每一層節(jié)點的平均值。與實際答案相差 10-5 以內(nèi)的答案可以被接受。
示例 1:輸入：root = [3,9,20,null,null,15,7]輸出：[3.00000,14.50000,11.00000]解釋：第 0 層的平均值為 3,第 1 層的平均值為 14.5,第 2 層的平均值為 11 。因此返回 [3, 14.5, 11] 。
題眼：每一層節(jié)點的平均值
思路：一般 層序遍歷的基礎(chǔ)上，計算每一層對應(yīng)的平均值
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、轉(zhuǎn)換為鏈式存儲root = tmpTree[0]parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親節(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下個節(jié)點的左孩子parent += 1return rootclass Solution:def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:que = deque()que.append(root)result = []while len(que) > 0:size = len(que)  # 當(dāng)前隊列長度==二叉樹一層的節(jié)點個數(shù)s = 0for _ in range(size):  # 一層遍歷node = que.popleft()s += node.valif node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result.append(s / size)return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.averageOfLevels(root))except EOFError:break

from typing import List, Optional, Union
from collections import deque
'''
515. 在每個樹行中找最大值
給定一棵二叉樹的根節(jié)點 root ，請找出該二叉樹中每一層的最大值。
示例 1:輸入: root = [1,3,2,5,3,null,9]輸出: [1,3,9]
題眼：二叉樹的層序遍歷
思路：一般 層序遍歷的基礎(chǔ)上，記錄每一行的最大值
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、轉(zhuǎn)換為順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)root = tmpTree[0]# 2、轉(zhuǎn)換為鏈式存儲：雙指針parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親節(jié)點有效if tmpTree[child] != None:  #  左孩子有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下個節(jié)點的左孩子parent += 1return rootclass Solution:def largestValues(self, root: Optional[TreeNode]) -> List[int]:# 情況1、樹為空if root == None:return []# 情況2、樹不為空que = deque()que.append(root)result = []while len(que) > 0:size = len(que)  # 當(dāng)前隊列長度==二叉樹一層的節(jié)點個數(shù)n = -float('inf')for _ in range(size):  # 一層遍歷node = que.popleft()n = max(n, node.val)if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result.append(n)return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.largestValues(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，返回每一層的最后一個元素

from typing import List, Optional, Union
from collections import deque
'''
199. 二叉樹的右視圖
給定一個二叉樹的 根節(jié)點 root，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點值。
示例 1:輸入：[1,2,3,null,5,null,4]輸出：[1,3,4]
題眼：從頂部到底部  從右側(cè)所能看到
思路：一般 層序遍歷的基礎(chǔ)上，返回每一層的最后一個元素
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、 順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、鏈式存儲：雙指針root = tmpTree[0]parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親結(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子節(jié)點存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下個節(jié)點的左孩子parent += 1return rootclass Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:# 情況1、樹為空if root == None:return []# 情況2、樹不為空que = deque()que.append(root)result = []while len(que) > 0:size = len(que)for i in range(size):  # 一層遍歷node = que.popleft()if i == size - 1:  # 添加每一層的最后一個元素result.append(node.val)if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.rightSideView(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，訪問每一層的每個元素時，都把第一個元素進行賦值即可

from typing import List, Optional, Union
from collections import deque
'''
513. 找樹左下角的值
給定一個二叉樹的 根節(jié)點 root，請找出該二叉樹的 最底層 最左邊 節(jié)點的值。
假設(shè)二叉樹中至少有一個節(jié)點。
示例 1:輸入: root = [2,1,3]輸出: 1
題眼：二叉樹的層序遍歷
思路：一般 層序遍歷的基礎(chǔ)上，訪問每一層的每個元素時，都把第一個元素進行賦值即可
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)root = tmpTree[0]# 2、鏈式存儲parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親結(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下一個節(jié)點的左孩子parent += 1return rootclass Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:que = deque()que.append(root)result = 0while len(que) > 0:size = len(que)for i in range(size):node = que.popleft()if i == 0:  # 總是獲取層序遍歷的每一層第一個值result = node.valif node.left != None:que.append(node.left)if node.right != None:que.append(node.right)return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.findBottomLeftValue(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，對結(jié)果的偶數(shù)個逆序一下

from typing import List, Optional, Union
from collections import deque
'''
103. 二叉樹的鋸齒形層序遍歷
給你二叉樹的根節(jié)點 root ，返回其節(jié)點值的 鋸齒形層序遍歷 。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。
示例 1:輸入：root = [3,9,20,null,null,15,7]輸出：[[3],[20,9],[15,7]]
題眼：基礎(chǔ)
思路：一般 層序遍歷的基礎(chǔ)上，對結(jié)果的偶數(shù)個逆序一下
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、轉(zhuǎn)換為順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、轉(zhuǎn)換為鏈式存儲：雙指針root = tmpTree[0]parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親節(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子節(jié)點存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下個節(jié)點的左孩子parent += 1  # 更新遍歷雙親節(jié)點return rootclass Solution:def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:# 情況1、樹為空if root == None:return []# 情況2、樹不為空que = deque()que.append(root)result = []while len(que) > 0:size = len(que)layer = []for _ in range(size):node = que.popleft()layer.append(node.val)if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result.append(layer)# 對結(jié)果的偶數(shù)個逆序一下for i in range(1, len(result), 2):result[i] = result[i][::-1]return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.zigzagLevelOrder(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，將每層的節(jié)點（除最后一個外）的next值指向下一個節(jié)點

from typing import List, Optional, Union
from collections import deque
'''
116. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針
給定一個 完美二叉樹 ，其所有葉子節(jié)點都在同一層，每個父節(jié)點都有兩個子節(jié)點。二叉樹定義如下：
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側(cè)節(jié)點。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有next 指針都被設(shè)置為 NULL。
示例 1:輸入：root = [1,2,3,4,5,6,7]輸出：[1,#,2,3,#,4,5,6,7,#]解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個 next 指針，以指向其下一個右側(cè)節(jié)點，如圖 B 所示。序列化的輸出按層序遍歷排列，同一層節(jié)點由 next 指針連接，'#' 標志著每一層的結(jié)束。
題眼：二叉樹的層序遍歷（滿二叉樹）
思路：一般 層序遍歷的基礎(chǔ)上，將每層的節(jié)點（除最后一個外）的next值指向下一個節(jié)點
'''class Node:def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = nextdef buildBinartTree(nums: List[Union[int]]) -> Optional[Node]:if len(nums) == 0:return []if len(nums) == 1:return Node(nums[0])# 1、轉(zhuǎn)換為順序存儲tmpTree = []for n in nums:tmpTree.append(Node(n))root = tmpTree[0]# 2、轉(zhuǎn)換為鏈式存儲parent, child = 0, 1while child < len(tmpTree):tmpTree[parent].left = tmpTree[child]  # 滿二叉樹左孩子一定有效child += 1tmpTree[parent].right = tmpTree[child]  # 滿二叉樹右孩子一定存在且有效child += 1parent += 1return rootclass Solution:def connect(self, root: Optional[Node]) -> Optional[Node]:# 情況1、樹為空if root == None:return root# 情況2、樹不為空que = deque()que.append(root)while len(que) > 0:size = len(que)pre = Nonefor i in range(size):node = que.popleft()if i == 0:  # 記錄每層第一個節(jié)點為prepre = nodeelse:  # 從每層第二個節(jié)點開始，都要給pre的next指針賦值pre.next = nodepre = nodeif node.left != None:que.append(node.left)if node.right != None:que.append(node.right)return rootif __name__ == "__main__":while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):nums.append(int(n))print(nums)except EOFError:break

一般 層序遍歷的基礎(chǔ)上，將每層的節(jié)點（除最后一個外）的next值指向下一個節(jié)點

from typing import List, Union, Optional
from collections import deque
'''
117. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針 II
給定一個二叉樹
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側(cè)節(jié)點。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有next 指針都被設(shè)置為 NULL。
示例 1:輸入：root = [1,2,3,4,5,null,7]輸出：[1,#,2,3,#,4,5,7,#]解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個 next 指針，以指向其下一個右側(cè)節(jié)點，如圖 B 所示。序列化輸出按層序遍歷順序（由 next 指針連接），'#' 表示每層的末尾。
題眼：二叉樹的層序遍歷（注意不是滿二叉樹）
思路：一般 層序遍歷的基礎(chǔ)上，將每層的節(jié)點（除最后一個外）的next值指向下一個節(jié)點
'''class Node:def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = nextdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[Node]:if len(nums) == 0:return Noneif len(nums) == 1:return Node(nums[0])# 1、轉(zhuǎn)換為順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(Node(n))else:tmpTree.append(None)root = tmpTree[0]# 2、轉(zhuǎn)換為鏈式存儲parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親節(jié)點有效性判斷if tmpTree[child] != None:  # 左孩子節(jié)點有效性判斷tmpTree[parent].left = tmpTree[child]child += 1if child < len(tmpTree) and tmpTree[child] != None:  # 左孩子節(jié)點存在且有效tmpTree[parent].right = tmpTree[child]child += 1parent += 1return rootclass Solution:def connect(self, root: Optional[Node]) -> Optional[Node]:# 情況1、樹為空if root == None:return root# 情況2、樹不為空que = deque()que.append(root)while len(que) > 0:size = len(que)pre = Nonefor i in range(size):node = que.popleft()if i == 0:  # 記錄每層第一個節(jié)點為prepre = nodeelse:  # 從每層第二個節(jié)點開始，都要給pre的next指針賦值pre.next = nodepre = nodeif node.left != None:que.append(node.left)if node.right != None:que.append(node.right)return rootif __name__ == "__main__":while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)print(nums)except EOFError:break

一般 層序遍歷的基礎(chǔ)上，輸出最大高度值，也就是二叉樹的高度值

from typing import List, Optional, Union
from collections import deque
'''
104. 二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例 1:輸入：[3,9,20,null,null,15,7]輸出：3
題眼：二叉樹的層序遍歷
思路：一般 層序遍歷的基礎(chǔ)上，輸出最大高度值
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)root = tmpTree[0]# 2、鏈式存儲parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親結(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下一個節(jié)點的左孩子parent += 1return rootclass Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# 情況1、樹為空if root == None:return 0# 情況2、樹不為空result = 0que = deque()que.append(root)while len(que) > 0:size = len(que)for _ in range(size):node = que.popleft()if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result += 1return result# 做完了計算完全二叉樹的節(jié)點數(shù)，用了帶return的遞歸法，有點感覺了，看看能否把這里的迭代法寫出來def maxDepthRecursive(self, root: Optional[TreeNode]) -> int:# 1、確定函數(shù)參數(shù)和返回值def maxDepth(node: Optional[TreeNode]) -> int:# 2、終止條件if node == None:return 0# 3、單次遞歸的操作leftN = maxDepth(node.left)     # 左rightN = maxDepth(node.right)   # 右return max(leftN, rightN) + 1   # 中return maxDepth(root)if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.maxDepth(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，輸出最小高度值（第一次遍歷到葉子節(jié)點的時候）

from typing import List, Optional, Union
from collections import deque
'''
111. 二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。
說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例 1:輸入：root = [3,9,20,null,null,15,7]輸出：2
題眼：二叉樹的層序遍歷
思路：一般 層序遍歷的基礎(chǔ)上，輸出最小高度值（第一次遍歷到葉子節(jié)點的時候）
'''class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:if len(nums) == 0:return Noneif len(nums) == 1:return TreeNode(nums[0])# 1、順序存儲tmpTree = []for n in nums:if n != 'null':tmpTree.append(TreeNode(n))else:tmpTree.append(None)root = tmpTree[0]# 2、鏈式存儲parent, child = 0, 1while child < len(tmpTree):if tmpTree[parent] != None:  # 雙親結(jié)點有效if tmpTree[child] != None:  # 左孩子節(jié)點有效tmpTree[parent].left = tmpTree[child]child += 1  # 指向右孩子if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效tmpTree[parent].right = tmpTree[child]child += 1  # 指向下一個節(jié)點的左孩子parent += 1return rootclass Solution:def minDepth(self, root: Optional[TreeNode]) -> int:# 情況1、樹為空if root == None:return 0# 情況2、樹不為空result = 0que = deque()que.append(root)while len(que) > 0:size = len(que)for _ in range(size):node = que.popleft()if node.left == None and node.right == None:return result + 1if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)result += 1return result# 做完了最大深度的遞歸，試試這個最小深度的，有陷阱！！！def minDepthRecursive(self, root: Optional[TreeNode]) -> int:# 1、確定函數(shù)參數(shù)和返回值def minD(node: Optional[TreeNode]) -> int:# 2、終止條件if node == None:return 0# 3、單次遞歸的操作leftN = minD(node.left)                         # 左rightN = minD(node.right)                       # 右# 當(dāng)一個左子樹為空，右不為空，這時并不是最低點if node.left == None and node.right != None:    # 中return 1 + rightN# 當(dāng)一個右子樹為空，左不為空，這時并不是最低點if node.left != None and node.right == None:return 1 + leftNreturn min(leftN, rightN) + 1return minD(root)if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):if n != 'null':nums.append(int(n))else:nums.append(n)root = buildBinaryTree(nums)print(obj.minDepth(root))except EOFError:break

一般 層序遍歷的基礎(chǔ)上，遍歷children部分

from typing import List, Optional, Union
from collections import deque
'''
559. N 叉樹的最大深度
給定一個 N 叉樹，找到其最大深度。
最大深度是指從根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點總數(shù)。
N 叉樹輸入按層序遍歷序列化表示，每組子節(jié)點由空值分隔（請參見示例）。示例 1:輸入：root = [1,null,3,2,4,null,5,6]輸出：3
題眼：二叉樹的層序遍歷
思路：一般 層序遍歷的基礎(chǔ)上，遍歷children部分
'''class Node:def __init__(self, val=None, children=None):self.val = valself.children = childrenclass Solution:def maxDepth(self, root: Optional[Node]) -> int:# 情況1、樹為空if root == None:return 0# 情況2、樹不為空result = 0que = deque()que.append(root)while len(que) > 0:size = len(que)for _ in range(size):node = que.popleft()if node.children != None:for child in node.children:que.append(child)result += 1return result