2021-10-26 leetcode 数据结构 N叉树的遍历 c++

在 N 叉树中，前序遍历指先访问根节点，然后逐个遍历以其子节点为根的子树。
上述三叉树的前序遍历是：A->B->C->E->F->D->G.

在 N 叉树中，后序遍历指前先逐个遍历以根节点的子节点为根的子树，最后访问根节点。
上述三叉树的后序遍历是：B->E->F->C->G->D->A.

N 叉树的层序遍历与二叉树的一致。通常，当我们在树中进行广度优先搜索时，我们将按层序的顺序进行遍历。
上述三叉树的层序遍历是：A->B->C->D->E->F->G.

和二叉树的遍历思路大致相同，不同点在二叉树是左右结点，而N叉树是children结点
前序和后序遍历思路参考 二叉树的前序遍历和后序遍历
层序遍历思路参考二叉树的层序遍历

leetcode 589.前序遍历

class Solution {
private:
    vector res;
public:
    void dfs(Node* root){
        if(!root)
            return ;
        res.push_back(root->val);
        int l = (root->children).size();
        for(int i = 0; i < l; i++)
            dfs(root->children[i]);
            
    }
    vector preorder(Node* root) {
        if(!root)
            return res;
        dfs(root);
        return res;
    }

};

leetcode 590.N 叉树的后序遍历

class Solution {
private:
    vector res;
public:
    void dfs(Node* root) { 
        if(!root)
            return ;
        int l = (root->children).size();
        for(int i = 0; i < l; i++)
            dfs(root->children[i]);
        res.push_back(root->val);
    }
    vector postorder(Node* root) {
        if(!root)
            return res;
        dfs(root);
        return res;
    }

};

leetcode 429.N 叉树的层序遍历

class Solution {
public:
    vector> levelOrder(Node* root) {
        vector> res;
        if(!root)
            return res;
        queue q;
        q.push(root);
        while(!q.empty()) {
            int l = q.size();
            vector temp;
            while(l--) {
                Node* node = q.front();
                temp.push_back(node->val);
                int len = (node->children).size();
                for(int i = 0; i < len; i++) 
                    q.push(node->children[i]);
                q.pop();
            }
            res.push_back(temp);
        }
        return res;
    }
};