【LeetCode】N叉樹的層序周遊

題目描述

給定一個 N 叉樹，傳回其節點值的層序周遊。 (即從左到右，逐層周遊)。

例如，給定一個 3叉樹 :

傳回其層序周遊:

[

[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/