589. N-ary Tree Preorder Traversal N 叉树的前序遍历

@TOC

# 题目描述

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?

N叉树的前序遍历。

# 解题方法

# 递归

Python代码如下：

``````"""
# 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]
"""
res = []
if not root:
return res
res.append(root.val)
for child in root.children:
res.extend(self.preorder(child))
return res
``````

C++代码如下：

``````/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> res;
if (!root) return res;
res.push_back(root->val);
for (Node* child : root->children) {
vector<int> child_vector = preorder(child);
res.insert(res.end(), child_vector.begin(), child_vector.end());
}
return res;
}
};
``````

# 迭代

Python代码如下：

``````"""
# 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]
"""
if not root: return []
stack = []
stack.append(root)
res = []
while stack:
node = stack.pop()
res.append(node.val)
stack.extend(node.children[::-1])
return res
``````

C++代码如下：

``````/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> res;
if (!root) return res;
stack<Node*> s;
s.push(root);
while (!s.empty()) {
Node* node = s.top(); s.pop();
if (!node) continue;
res.push_back(node->val);
for (int i = node->children.size() - 1; i >= 0; --i) {
s.push(node->children[i]);
}
}
return res;
}
};
``````

# 日期

2018 年 7 月 12 日 —— 天阴阴地潮潮，已经连着两天这样了 2018 年 11 月 5 日 —— 打了羽毛球，有点累 2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？