题目

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

例如，给定一个 3叉树 :

image.png

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

方案一（递归）

  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. class Solution:
  9.     def preorder(self, root: 'Node') -> [int]:
  10.         if not root:
  11.             return []
  12.         if not root.children:
  13.             return [root.val]
  15.         ret = [root.val]
  16.         for node in root.children:
  17.             ret.extend(self.preorder(node))
  19.         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. class Solution:
  9.     def preorder(self, root: 'Node') -> [int]:
  10.         if not root:
  11.             return []
  13.         stack = [root]
  14.         ret = []
  16.         while stack:
  17.             node = stack.pop()
  18.             ret.append(node.val)
  19.             if node.children:
  20.                 node.children.reverse()
  21.                 stack.extend(node.children)
  22.         return ret

原文

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