题目
难度：★★☆☆☆
类型：树
给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :
N叉树
返回其前序遍历: [1,3,5,6,2,4]。
说明: 递归法很简单，你可以使用迭代法完成此题吗?
解答
方案1：递归
class Solution:
def preorder(self, root):
def pre_order(node, l):
"""
N叉树的前序遍历
:param node: 输入结点
:param l: 结果列表
:return:
"""
if node: # 如果输入结点不为空
l.append(node.val) # 添加结点值到结果列表
for child in node.children: # 对每一棵子树做前序遍历
pre_order(child, l)
res = []
pre_order(root, res)
return res
上述方法的紧凑写法：
class Solution:
def preorder(self, root):
return [root.val]+sum([self.preorder(i) for i in root.children], []) if root else []
方案2：迭代
class Solution:
def preorder(self, root):
if root is None:
return []
stack = [root]
res = []
while len(stack):
node = stack.pop()
res.append(node.val)
temp = []
for i in node.children:
temp.append(i)
if len(temp):
temp.reverse()
stack.extend(temp)
return res
如有疑问或建议，欢迎评论区留言~
