力扣589——N叉树的前序遍历

力扣589——N叉树的前序遍历

 递归做法：         做法与二叉树相似，用一个for循环递归每个children

class Solution {
public:
    vector preorder(Node* root) {
        vector vec;
        pre(root,vec);
        return vec;
    }
    void pre(Node *root,vector &vec){
        if(root==nullptr)return ;
        vec.push_back(root->val);
        for(auto ch : root->children){
            pre(ch,vec);
        }
    }
};

非递归做法：         也是与二叉树类似，用for循环每次使cur->children入栈，需要注意的是入栈顺序应该是从右往左，所以要先用reverse()函数反转cur->childre

class Solution {
public:
    vector preorder(Node* root) {
        vector vec;
        stackstk;
        stk.push(root);
        while(!stk.empty()){
            Node *cur=stk.top();
            stk.pop();
            vec.push_back(cur->val);
            reverse(cur->children.begin(),cur->children.end());//因为栈是先进后出的，所以要将节点的子节点逆序入栈，才能保证其子节点出栈的顺序为从左到右
            for(auto ch : cur->children){
                stk.push(ch);
            }
        }
        return vec;
    }
};