2025/8/28 二叉樹的層序遍歷

方法一：迭代+隊列

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = collections.deque([root])
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

知識點：

① python隊列（Queue）

實現方式	數據結構	適用場景	是否線程安全
collections.deque	雙端隊列	常用，推薦	否
queue.Queue	標準隊列	多線程通信時用	是
`list` 模擬隊列	一般隊列	小規模簡單用法	否，性能低

（a）最常用：collections.deque

from collections import deque

queue = deque()

# 入隊
queue.append(1)
queue.append(2)

# 出隊
x = queue.popleft()  # FIFO：1 先出

print(x)         # 1
print(queue)     # deque([2])

append()：尾部插入

appendleft()：頭部插入

pop()：尾部彈出

popleft()：頭部彈出（? 隊列常用）

②len(queue) 會不會在每次循環中都重新計算？

for _ in range(len(queue)):

不會。

len(queue) 是在進入 range(...) 時就計算好了，range(...) 在整個 for 循環開始時只計算一次，range 生成的是一個固定的整數序列（迭代器）。
后續即使 queue 變了，range(...) 里面的長度也不會變。

方法二：遞歸

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []

        def traverse(node, level):
            if not node:
                return
            
            if len(result) == level:
                result.append([])

            result[level].append(node.val)
            traverse(node.left, level+1)
            traverse(node.right, level+1)
        
        traverse(root, 0)
        return result

2. 107. 二叉樹的層序遍歷 II - 力扣（LeetCode） ?

列表反轉知識點：2025/5/12 【二叉樹】前中后序迭代遍歷 LeetCode144， 94， 145 【√】 - axuu - 博客園

（1）最常見的三種列表反轉方式

①方法1：使用切片[::-1]

特點：返回新列表，原列表不變

②方法2：使用內置函數reversed() + list()

lst = [1, 2, 3, 4]
reversed_lst = list(reversed(lst))

特點：返回新列表，原列表不變，可用于字符串、元組等。

s = "hello"
print("".join(reversed(s)))  # 'olleh'

③方法3：使用list.reverse() 方法（原地反轉）

lst = [1, 2, 3, 4]
lst.reverse()
print(lst)  # [4, 3, 2, 1]

特點：無返回值，就地反轉原列表

錯誤寫法：

lst = [1, 2, 3]
lst = lst.reverse()  # ? lst 會變成 None！

list.reverse() 是原地操作，不返回新列表，只能單獨調用：

（2）三種方法的對比總結表

方法	是否返回新列表	是否修改原列表	返回類型	是否推薦
lst[::-1]	? 是	? 否	list
list(reversed(lst))	? 是	? 否	list
lst.reverse()	? 否（返回 None）	? 是	None（就地修改）	原地修改，節省內存

（3）應用場景舉例

①反轉字符串（用切片或 reversed）

s = "hello"
print(s[::-1])  # 'olleh'
print("".join(reversed(s)))  # 'olleh'

字符串不可變，不可原地反轉

3. 199. 二叉樹的右視圖 - 力扣（LeetCode） ?

代碼1，在基本的層序遍歷代碼上做小小的修改

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

代碼2

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

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return right_view

4. 637. 二叉樹的層平均值 - 力扣（LeetCode）?

知識點：

①

在 LeetCode 上：

mean 是 statistics 模塊的一部分，而 LeetCode 自動為用戶導入了這個模塊，可以直接使用 mean()。
在 LeetCode 上，很多常用模塊（比如 statistics、math、collections 等）都已經預先導入，用戶可以直接使用它們。

在本地環境中：

如果在本地運行代碼，需要先導入 statistics 模塊才能使用 mean()：

import statistics

numbers = [1, 2, 3, 4, 5]
average = statistics.mean(numbers)  # 需要顯式導入
print(average)  # 3.0

②python中求平均數（averages）的基本方法：使用sum() 和 len()

numbers = [1, 2, 3, 4, 5]
average = sum(numbers) / len(numbers)
print(average)  # 3.0

注意：如果列表為空，直接計算 len(numbers) 會導致 ZeroDivisionError（除零錯誤）。需要做檢查，確保列表不為空。

5. 429. N 叉樹的層序遍歷 - 力扣（LeetCode）

解法一：迭代+隊列

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = collections.deque([root])

        while queue:
            level_size = len(queue)
            level = []

            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)

                for child in node.children:
                    queue.append(child)
            
            result.append(level)
            
        return result

解法2：遞歸法

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []

        result = []

        def traverse(node, level):
            if not node:
                return

            if len(result) == level:
                result.append([])

            result[level].append(node.val)
            for child in node.children:
                traverse(child, level+1)

        traverse(root, 0)
        return result

知識點：

①N叉樹的定義代碼

class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children

②類型注解（Type Hint）

類型注解就是：給變量、函數參數和返回值標注“它是什么類型”。

類型注解 = 變量 + 類型提示，不會影響代碼執行，只是對人和工具的提示。

children: Optional[List['Node']] = None

這是 Python 的 類型注解 + 默認值 組合寫法

（a）對變量 children 添加類型注解，

（b）Optional[...]

是 typing 模塊中的一個泛型類型，含義是：

可以是某種類型，也可以是 None。

即：

Optional[X] == Union[X, None]

所以：

Optional[List['Node']]

表示：

children 這個變量 要么是一個 Node 類型的列表，要么就是 None（即沒有子節點）。

Optional[str] 就是 str | None（可以是字符串，也可以是 None）

* 類型注解的一種類型1：聯合類型（Union）

from typing import Union

def parse(x: Union[int, str]) -> str:
    return str(x)

**類型注解的一種類型2：遞歸結構（如'Node'）

class Node:
    def __init__(self, val: int, children: List['Node']):
        self.val = val
        self.children = children

（c）List['Node']

表示這是一個列表類型（List），每個元素都是 'Node' 類型。

·為什么要加引號 'Node'？因為 Node 這個類還沒有定義完

·這是 前向引用（forward reference），用于在類體中引用自己。

（d）= None

這是 Python 中的默認參數值寫法，表示：如果用戶在創建對象時 沒有顯式傳入 children 參數，那么默認就用 None。

（e）總結該注解代碼的全部含義：

變量 children 是一個列表，里面的每個元素都是 Node 類型；

但也可以是 None（表示沒有子節點）；

如果不傳這個參數，默認就是 None。

③前向引用

def levelOrder(self, root: 'Node'):

（a）為啥 'Node' 外面要加引號？

回答：因為在函數定義里引用了 Node 類型，但是 Node 類可能還沒定義好。
所以加引號 'Node' 表示：“我現在先告訴你我要用 Node 類型，但我后面再定義它。”
這就叫做：前向引用（forward reference）。

當類相互引用或遞歸類型（即類內部引用自身）時，需要使用前向引用。

（b）為什么不能直接寫 root: Node？

錯誤寫法：

def levelOrder(self, root: Node):  # 這時候 Node 還沒定義

在 Python 解釋器還沒有“看到”Node 類的定義前，它不知道 Node 是啥，就會報錯。

正確寫法：用引號包起來

def levelOrder(self, root: 'Node'):

這樣寫，'Node' 會被當作一個**“延遲字符串”**處理。

Python 會等整個程序都加載完之后，再把 'Node' 當作真正的類型來用。

可以理解成提前“打個招呼”：Node 我后面再解釋，現在先用引號占個位。

6. 515. 在每個樹行中找最大值 - 力扣（LeetCode）

知識點：

①python中表示正負無窮

max_val = float('-inf')

是在 Python 中定義一個初始值為“負無窮”的變量，常用于找最大值的初始化。

float('-inf') 是一個合法的 Python 浮點數（float）值，表示負無窮大（-∞）。

neg_inf = float('-inf')  # -∞
pos_inf = float('inf')   # +∞

另外的表示：

import math

math.inf       # +∞
-math.inf      # -∞

② max() 函數是 Python 中最常用的內置函數之一

基本語法：

max(a, b, c, ...)
max(iterable)

7. 116. 填充每個節點的下一個右側節點指針 - 力扣（LeetCode）

注意按照題意：

用戶要實現的功能：連接每一層的相鄰節點

如果用戶按題目要求把樹連接好了，由平臺用一個特殊的層序遍歷方式檢查

解法一：迭代+隊列

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root

        queue = collections.deque([root])

        while queue:
            prev = None

            for _ in range(len(queue)):
                node = queue.popleft()

                if prev:
                    prev.next = node

                prev = node
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # prev.next = None
            
        return root

對于每一層最后一個結點，根本不需要顯式設置 .next = None，因為默認它就是 None。

解法2：完美二叉樹下的遞歸解法（116）

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root or not root.left:
            return root
        root.left.next = root.right
        # 在完美二叉樹中，把相鄰兩個父節點的孩子連接起來。
        if root.next:
            root.right.next = root.next.left
        self.connect(root.left)
        self.connect(root.right)
        return root

8. 117. 填充每個節點的下一個右側節點指針 II - 力扣（LeetCode）

上面116題的代碼可以解決。

116題是完美二叉樹（每個節點都有兩個孩子，整棵樹是滿的）

117題目是普通二叉樹（可以是任意形狀，非滿、不平衡）

9. 104. 二叉樹的最大深度 - 力扣（LeetCode）

10.111. 二叉樹的最小深度 - 力扣（LeetCode）

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

總結：二叉樹的層序遍歷，就是圖論中的廣度優先搜索在二叉樹中的應用，需要借助隊列來實現。

posted on 2025-08-28 23:00 axuu 閱讀(9) 評論(0) 收藏舉報