Given an n-ary tree, return the postorder traversal of its nodes' values.
For example, given a 3-ary tree:
Return its postorder traversal as: [5,6,3,2,4,1].
这个题目思路就是跟LeetCode questions conlusion_InOrder, PreOrder, PostOrder traversal里面postorder traversal很像, 只是将left child 和right child变成了children而已,
当然这里假设的是children的顺序是从左到右的.
code
1) recursive
class Solution:
def naryPostOrderTraversal(self, root):
def helper(root):
if not root: return
for each in root.children:
helper(each)
ans.append(root.val)
ans = []
helper(root)
return ans
2) iterable
class Solution:
def naryPostOrderTraversal(self, root):
if not root: return []
stack, ans = [(root, False)], []
while stack:
node, visited = stack.pop()
if visited:
ans.append(node.val)
else:
stack.append((node, True))
for each in node.children[::-1]:
stack.append((each, False))
return ans