Given an n-ary tree, return the preorder traversal of its nodes‘ values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4].
Note: Recursive solution is trivial, could you do it iteratively?
Recursion Method:
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution(object):
def preorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
l=[]
def subpreorderfun(r):
if r:
l.append(r.val)
for c in r.children:
subpreorderfun(c)
subpreorderfun(root)
return l
Iteration Method:
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution(object):
def preorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
l=[]
q=[root]
if root:
p=[]
while q:
a=q.pop(0)
l.append(a.val)
for c in a.children:
p.append(c)
n=len(p)
for i in range(n):
q=[p.pop()]+q
return l
[LeetCode&Python] Problem 589. N-ary Tree Preorder Traversal
原文：https://www.cnblogs.com/chiyeung/p/9744423.html