给定一个 N 叉树，返回其节点值的前序遍历。
N叉树的定义如下
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
例如
给定一个 3叉树 :
1
/|\
3 2 4
/ \
5 6
返回其前序遍历: [1,3,5,6,2,4]。
说明:
递归法很简单，你可以使用迭代法完成此题吗?
思路1
首先采用递归法，假设当前节点不为空，则将当前节点存入结果集中
遍历所有孩子节点，向每个孩子节点进行递归
递归法具体代码
vector<int> res; // 结果集
vector<int> preorder(Node* root) {
if(root == NULL){ //判断当前节点不为空
return res;
}
res.push_back(root->val); //将当前节点加入结果集
for(int i = 0; i < root->children.size(); i++){ //遍历所有孩子节点
preorder(root->children[i]); //递归进入孩子节点
}
return res; //返回结果
}
思路2
使用迭代法，不使用递归调用的方式。
使用栈来辅助，我们一层一层进行遍历
假设此时我们在处理第n行的节点p1
先把p1的所有兄弟节点（p2，p3，p4，...）存入栈中，等待后续使用
接着把p1存入结果集中，遍历p1所有孩子节点（pc1，pc2，...），存入栈中，等待后续使用
取出p1的最左孩子节点pc1，依次往下处理，假设此时p1的所有孩子节点都处理完毕了
从栈中取出p2，以此类推使用。
因此整个栈的存放顺序为
栈底|pn, pn-1,...,p2,pcn,...,pc2,pc1
也就是说，存栈的时候，局部逆序存储
迭代法具体代码
vector<int> res;
stack<Node*> s;
vector<int> preorder(Node* root) {
while(root != NULL){ // 该判断用来规避初始为空的情况
res.push_back(root->val); // 当前节点存入结果集
//逆序存入所有孩子节点
for(int i = root->children.size() - 1; i >= 0; i--){
s.push(root->children[i]);
}
//从栈中取出栈顶节点
if(s.empty()){ //栈空，说明遍历完成
break;
}
root = s.top();
s.pop();
}
return res;
}
