05 N叉樹的后序，中序遍歷

遞歸寫法：

寫法1：標準 DFS + extend 收集結果

class Solution: 
    def postorder(self, root: 'Node') -> List[int]: 
        if not root: 
            return []
        
        result = [] 
        for child in root.children:
            result.extend(self.postorder(child))
        result.append(root.val) 
        return result

知識點：

①extend函數

extend() 是 Python list 的一個方法，用來將一個可迭代對象中的元素逐個添加到列表的末尾。

（a）和 append() 的區別

操作	含義	結果
append(x)	把 `x` 作為一個整體元素加進列表	列表長度增加 1，添加的是對象本身
extend(iterable)	把 `iterable` 的每個元素加進列表	列表長度增加 `len(iterable)` 個元素

a = [1, 2]
b = [3, 4]

a.append(b)
print(a)        # ?? [1, 2, [3, 4]]     ? 多了一層嵌套

a = [1, 2]
a.extend(b)
print(a)        # ?? [1, 2, 3, 4]       ? 平鋪展開

append() 是整體添加（會嵌套）

extend() 是平鋪展開（逐個加）

（b）支持哪些類型？

只要是可迭代對象，都可以用 extend()：

a = [1, 2]
a.extend((3, 4))       # ? 元組
a.extend({5, 6})       # ? 集合（無序）
a.extend("78")         # ? 字符串會被逐字符拆分
a.extend(range(2))     # ? range

print(a)  # 結果可能是 [1, 2, 3, 4, 5, 6, '7', '8', 0, 1]

（c）常見用法

1?? 合并兩個列表（推薦用 extend()）

a = [1, 2]
b = [3, 4]
a.extend(b)  # ? 比 a = a + b 更快（原地修改）

2?? 遞歸遍歷中收集子結果

for child in root.children:
    result.extend(self.postorder(child))

每個子節點的遍歷結果是一個 List
用 extend() 把這些子結果合并成一個完整結果

（d）注意：

extend() 是就地修改，返回 None；所以不要寫 a = a.extend(b)；

字符串會被按字符拆分，extend("abc") → ['a', 'b', 'c']

（e）易錯

a = [1, 2]
a.extend([[3, 4]])
print(a)  # ?輸出是什么？

# ?? 答案：[1, 2, [3, 4]]，因為傳的是包含列表的列表

寫法2：寫dfs函數

class Solution: 
    def postorder(self, root: 'Node') -> List[int]: 
        result = []
        
        def dfs(node):
            if not node:
                return
            for child in node.children:
                dfs(child)
            result.append(node.val)
        dfs(root)
        return result

589. N 叉樹的前序遍歷 - 力扣（LeetCode）

遞歸寫法：

寫法1：標準 DFS + extend 收集結果（「返回值式遞歸 + extend 合并結果」）

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        result = []
        result.append(root.val)
        for child in root.children:
            result.extend(self.preorder(child))
        return result

每個遞歸函數 postorder(child) 會返回一個 新的列表（返回子樹結果），所以要用 extend() 把它們“拼”在一起；

每次 result.extend(...) 拼接構建結果，導致效率較低（頻繁拼接、創建新列表）；

創建了很多中間列表（每次遞歸返回一個新列表），對于大樹可能有性能問題（尤其是深度大 or 子樹多）；

結構更函數式、遞歸風格：寫法短、遞歸思維清晰。

寫法2：寫dfs函數（「過程式遞歸 + 外部累加結果」）

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

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        result = []
        
        def dfs(node):
            if not node:
                return
            result.append(node.val)
            for child in node.children:
                dfs(child)
        
        dfs(root)
        return result

遞歸函數無返回值，直接修改result；

所有子樹的遞歸過程，都共享同一個 result，直接在遍歷過程中 append，不返回中間列表，更貼近真實 DFS

優點：效率高，只構造一個列表，沒有中間拼接；控制力強，方便加各種邏輯（比如層數、路徑等）

缺點：result 是外部變量，不是純函數式（副作用略多）；不適合做成模塊復用（比如要寫一個純粹的遞歸函數庫）

posted on 2025-09-05 12:23 axuu 閱讀(7) 評論(0) 收藏舉報

刷新頁面返回頂部