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: if each: stack.append((each, False)) return ans
[LeetCode] 590. N-ary Tree Postorder Traversal_Easy
原文：https://www.cnblogs.com/Johnsonxiong/p/9349045.html