【LeetCode】N叉树的层序遍历

曾经终败给现在 2021-11-01 11:12 278阅读 0赞

#### 题目描述 ####

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。  
例如，给定一个 3叉树 :  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5XzY2OTk_size_16_color_FFFFFF_t_70]  
返回其层序遍历:

> \[  
> \[1\],  
> \[3,2,4\],  
> \[5,6\]  
> \]

说明:

1.  树的深度不会超过 1000。
2.  树的节点总数不会超过 5000。

#### 解题思路 ####

1.  用两个队列，一个队列存节点的value值，另一个队列存节点的层数，节点队列出队的将它的孩子节点和层数带入队列，并且当前节点的层数队列同时出队，从而输出正确的二位数组。
2.  用一个队列和一个一维数组，当队列不为空时当前队列的长度sz就是当前层数节点的个数，此时将出队的sz个放入同一个一维数组中，再将这些一维数组依次插入二维数组中即可，代码如下：

#### 完整代码 ####

/*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };
    */
    class Solution {
    public:
        vector<vector<int>> levelOrder(Node* root) {
            
            vector<vector<int>> treeVec;
            if(root==NULL)
                return treeVec;
            //根节点入队
            queue <Node*> q;
            q.push(root);
            while(!q.empty())
            {
                int sz=q.size(); //计算当前队列的长度
                vector<int> rowNode;
                //层节点入队并将层节点放入一维数组 
                while(sz--)
                {
                    Node* curNode=q.front();
                    q.pop();
                    rowNode.push_back(curNode->val);
                    for(auto &child:curNode->children)
                        q.push(child);
                }
                treeVec.push_back(rowNode);
            }
            return treeVec;
        }
    };

#### 原题链接 ####

https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/comments/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5XzY2OTk_size_16_color_FFFFFF_t_70]: /images/20211101/4cb770a5331443a28d5619f8768f2bc5.png