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

例如，给定一个 3叉树 :

 

 

 

 

 

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

 

说明: 递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal

递归：

1 void process(Node* root,vector
     
       &ans) { 2     ans.push_back(root->val); 3     int n = root->children.size(); 4  5     for(int i = 0; i < n; i++) 6     { 7         process(root->children[i],ans); 8     } 9 }10 vector
      
        preorder(Node* root) {11     vector
       
         ans;12     if(root)13         process(root,ans);14     return ans;15 }
       
      
     

迭代：

1 /* 2 // Definition for a Node. 3 class Node { 4 public: 5     int val; 6     vector
     
       children; 7  8     Node() {} 9 10     Node(int _val, vector
      
        _children) {11         val = _val;12         children = _children;13     }14 };15 */16 class Solution {17 public:18     vector
       
         preorder(Node* root) {19         vector
        
          ans;20         if(!root) return ans;21         stack
         
           nodeStack;22         nodeStack.push(root);23         while(!nodeStack.empty()) {24             Node* node = nodeStack.top();25             ans.push_back(node->val);26             nodeStack.pop();27             int n = node->children.size();28             for(int i = n-1; i >= 0 ; i--)29             {30                 nodeStack.push(node->children[i]);31             }32         }33         return ans;34     }35 };