LeetCode刷题（116）～N叉树的前序遍历【递归 ｜ 迭代】

题目描述

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

例如，给定一个 3叉树 :

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

  

 

  
1
 

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

解答 By 海轰

提交代码（递归）

 vector<int> ans; vector<int> preorder(Node* root) { if(root==NULL) return ans; ans.push_back(root->val); if(root->children.size()!=0) { for(int i=0;i<root->children.size();++i) preorder(root->children[i]); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

运行结果

提交代码（递归）

 vector<int> ans; vector<int> preorder(Node* root) { if(root==NULL) return ans; ans.push_back(root->val); for(auto child:root->children) preorder(child); return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

运行结果

提交代码（迭代）

vector<int> preorder(Node* root) { vector<int> ans; stack<Node*> s; if(root==NULL) return ans; s.push(root); while(!s.empty()) { Node* temp=s.top(); ans.push_back(temp->val); s.pop(); reverse(temp->children.begin(),temp->children.end()); for(auto child:temp->children) s.push(child); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

提交代码（迭代 优化）

vector<int> preorder(Node* root) { vector<int> ans; stack<Node*> s; if(root==NULL) return ans; s.push(root); while(!s.empty()) { Node* temp=s.top(); ans.push_back(temp->val); s.pop(); for(int i=temp->children.size()-1;i>=0;--i) s.push(temp->children[i]); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108342480