日野弥生：勉強しよう
LeetCode 589 - N 叉树的前序遍历
发表于2025年03月27日
本题递归法和二叉树的前序遍历无异，只是child变成了一个列表。
"""
# 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 preorderImpl(root: 'Node'):
if not root:
return
result.append(root.val)
for chd in root.children:
preorderImpl(chd)
preorderImpl(root)
return result迭代法的思路和二叉树也类似，只是需要注意进栈的子树的顺序。
class Solution:
def preorder(self, root: 'Node') -> List[int]:
result = []
stack = deque()
while root or stack:
if root:
result.append(root.val)
if root.children:
# 把所有子树都进栈后出栈第一个子树
for i in reversed(root.children):
stack.append(i)
root = stack.pop()
else:
# 遍历到叶子时，把当且节点值置空
root = None
elif stack:
root = stack.pop()
return result