題目描述
給定一個 N 叉樹,傳回其節點值的層序周遊。 (即從左到右,逐層周遊)。
例如,給定一個 3叉樹 :
傳回其層序周遊:
[
[1],
[3,2,4],
[5,6]
]
說明:
- 樹的深度不會超過 1000。
- 樹的節點總數不會超過 5000。
解題思路
- 用兩個隊列,一個隊列存節點的value值,另一個隊列存節點的層數,節點隊列出隊的将它的孩子節點和層數帶入隊列,并且目前節點的層數隊列同時出隊,進而輸出正确的二位數組。
- 用一個隊列和一個一維數組,當隊列不為空時目前隊列的長度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/