[数据结构与算法]2021-10-26 leetcode 数据结构 N叉树的遍历 c++

N叉树的遍历

前序遍历

在 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.前序遍历

/*
// 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 {
private:
    vector<int> 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<int> preorder(Node* root) {
        if(!root)
            return res;
        dfs(root);
        return res;
    }

};

后序遍历

leetcode 590.N 叉树的后序遍历

/*
// 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 {
private:
    vector<int> 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<int> postorder(Node* root) {
        if(!root)
            return res;
        dfs(root);
        return res;
    }

};

层序遍历

leetcode 429.N 叉树的层序遍历

/*
// 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<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if(!root)
            return res;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            int l = q.size();
            vector<int> 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;
    }
};