题目重点：Oracle IC2 题目明确提出 DFS 找所有叶节点；本文定义有序 N 叉树训练输入并证明左到右遍历。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入为有序 N 叉树，节点 children 的顺序定义输出顺序；无子节点即叶，根也可能是叶。
- 返回叶节点的 value；空树返回空列表。树无环且节点不共享；图输入需另加 visited。
解题路线
- 迭代 DFS 用栈保存待访问节点；为了按 children 从左到右访问，入栈时逆序压入。
- 弹出节点若 children 为空就把值加入答案，否则只扩展其子节点。
- 不需要额外按深度排序；若题目要求按层或从右到左，遍历规则须调整。
手动走一遍
根 1 的子节点依次是 2、3、4，节点 2 又有孩子 5、6；压栈 4、3、2 后先访问 2，再得到叶 5、6，随后 3、4，结果 [5,6,3,4]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Collect leaves of an ordered N-ary tree from left to right."""
class Node:
def __init__(self, value: int, children: list["Node"] | None = None):
self.value = value
self.children = children or []
def collect_leaves(root: Node | None) -> list[int]:
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
if not node.children:
result.append(node.value)
else:
stack.extend(reversed(node.children))
return result
复杂度
每个节点访问一次 O(N)；显式栈最坏 O(N)，输出 L 个叶还需 O(L)。
易错点与追问
容易失分的边界
- 顺序压 children 到 LIFO 栈，意外得到右到左。
- 把只有一个根节点的树误判为无叶。
- 未问清返回节点对象还是节点值。
继续深挖
- 若要按层收集叶节点，应换什么遍历？
- 树很深时递归 DFS 的栈风险如何避免？
- 共享子树或环出现时，是否应对节点去重？
