当前位置：首页 > news >正文

2025/09/05 N叉树的后序，中序遍历

news 2025/11/5 17:01:43

590. N 叉树的后序遍历 - 力扣（LeetCode）

递归写法：

写法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))     # ✅ rangeprint(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:returnfor 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 = valself.children = children
"""class Solution:def preorder(self, root: 'Node') -> List[int]:result = []def dfs(node):if not node:returnresult.append(node.val)for child in node.children:dfs(child)dfs(root)return result