题目

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树:

image.png

返回其后序遍历:[5, 6, 3, 2, 4, 1].

方案一（递归）

  1. """
  2. # Definition for a Node.
  3. class Node:
  4.     def __init__(self, val=None, children=None):
  5.         self.val = val
  6.         self.children = children
  7. """
  8. def postorder(root: 'Node') -> [int]:
  9.     if not root:
  10.         return []
  11.     if not root.children:
  12.         return [root.val]
  14.     ret = []
  15.     for child in root.children:
  16.         ret.extend(self.postorder(child))
  17.     ret.append(root.val)
  18.     return ret

方案二（迭代）

  1. """
  2. # Definition for a Node.
  3. class Node:
  4.     def __init__(self, val=None, children=None):
  5.         self.val = val
  6.         self.children = children
  7. """
  8. def postorder(root: 'Node') -> [int]:
  9.     if not root:
  10.         return []
  11.     stack = [root]
  12.     visited = set()
  13.     ret = []
  14.     while stack:
  15.         node = stack.pop()
  16.         if node not in visited and node.children:
  17.             visited.add(node)
  18.             stack.append(node)
  19.             stack.extend(node.children[::-1])
  20.         else:
  21.             ret.append(node.val)
  22.     return ret

原文

https://leetcode-cn.com/explore/learn/card/n-ary-tree/159/traversal/621/