Easy
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-ary数是根节点可拥有n个子节点的树，比如一个3-ary树如图所示。求出n-ary树的前序遍历。
前序遍历：根节点->左子树->右子树
方法一：递归
递归的将节点的值存入结果向量中
代码如下：
class Solution { public: vector<int> preorder(Node* root) { if (!root)return {}; vector<int> res; res.push_back((*root).val); if (!(*root).children.empty()) { int len = ((*root).children).size(); for (int i = 0; i < len; ++i) { vector<int> temp = preorder((*root).children[i]); res.insert(res.end(), temp.begin(), temp.end()); } } return res; } };
方法二：迭代法
使用堆来记录节点，然后逐个节点深入。这里要注意的是，因为是前序排列，所以要按照右子树->左子树的顺序将各节点放入stack中。
代码如下：
class Solution { public: vector<int> preorder(Node* root) { if (!root)return {}; vector<int> res; stack<Node*> s; s.push(root); while (!s.empty()) { Node* temp = s.top(); res.push_back(s.top()->val); s.pop(); int len = temp->children.size(); for (int i = len-1; i >= 0; --i) { s.push(temp->children[i]); } } return res; } };
ps一点个人想法：逐层遍历时使用queue更方便，其他时候使用stack。
[LeetCode] 589. N-ary Tree Preorder Traversal
原文：https://www.cnblogs.com/cff2121/p/11466893.html