589. N叉树的前序遍历

给定一个 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;
}