589题

方法一：递归方法与429题递归方法一致遍历顺序一致，只是429题通过层数d将所遍历的数放入了不同层

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> preorder(Node* root) {
        if(root==NULL){
            return result;
        }
        result.push_back(root->val);
        for(auto&it:root->children){
            preorder(it);
        }
        return result;
    }
    vector<int>result;
};

方法二：使用迭代的方法，emplace() 函数的功能是可以直接将参数传给对象的构造函数，新增加了emplace() 函数和 emplace_back() 函数，用来实现insert() 函数和 push_back() 函数的功能

class Solution {
public:
    vector<int> preorder(Node* root) {
        if(root==NULL){
            return result;
        }
        Node* head;
        s1.push(root);
        while(!s1.empty()){
            head=s1.top();
            s1.pop();
            result.push_back(head->val);
            for(auto it=head->children.rbegin();it!=head->children.rend();it++){//c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
                                                                                //c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置
                s1.emplace(*it);//这里需要解引用是因为it指向的是指向children指针
            }
        }
        return result;
    }
    vector<int>result;
    stack<Node*>s1;
};