說(shuō)明
連續(xù)在LeetCode中看到好幾個(gè)類似的題目，核心思想就是樹的廣度優(yōu)先搜索(BFS)滓彰，并在搜索的過(guò)程中記錄每一層的值怕享。
以LeetCode中的N-ary Tree Level Order Traversal為例：
Description
Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example, given a 3-ary tree:
We should return its level order traversal:
[
[1],
[3,2,4],
[5,6]
]
解析
利用隊(duì)列使用BFS。設(shè)res為要返回的2維數(shù)組, vec為當(dāng)前訪問(wèn)層的元素的1維數(shù)組绽昼。
- count為當(dāng)前層的節(jié)點(diǎn)數(shù)量芭商，初始化為0派草，newCount為新加入的一層的節(jié)點(diǎn)數(shù)量，初始化為0蓉坎，c為當(dāng)前訪問(wèn)層的第幾個(gè)元素澳眷，初始化為0.
- 根節(jié)點(diǎn)入隊(duì)胡嘿，++count, 根節(jié)點(diǎn)元素加入到vec中
- 如果c等于count,將1維數(shù)組vec加入到res中蛉艾，并使 count = newCount, c = 0, newCount = 0, 再清空vec
- 隊(duì)列中的第一個(gè)元素出隊(duì)，并賦值給p衷敌，對(duì)于p中的每一個(gè)子節(jié)點(diǎn)勿侯，如果不為空則進(jìn)隊(duì)并使newCount = newCount+1
- 節(jié)點(diǎn)p的元素加入到vec中， 并讓 c = c + 1
- 重復(fù)步驟3-5直到隊(duì)列為空
- 如果count大于0缴罗，則將vec中加入到res中
時(shí)間復(fù)雜度： O(n) n為節(jié)點(diǎn)的數(shù)量
C++實(shí)現(xiàn)
/*
// Definition for a Node.
class Node {
public:
int val = NULL;
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>> res;
if(root == NULL)
return res;
int count = 0;
int newCount = 0;
int c = 0;
vector<int> vec; // all node`val at same level
queue<Node*> q;
q.push(root);
count = 1;
while(!q.empty()){
if(c == count){
res.push_back(vec);
vec.clear();
count = newCount;
c = 0;
newCount = 0;
}
auto p = q.front();
q.pop();
vec.push_back(p->val);
for(int i = 0; i < p->children.size(); ++i){
if(p->children[i] != NULL){
q.push(p->children[i]);
++newCount;
}
}
++c;
}
if(count){ // last leavel values
res.push_back(vec);
}
return res;
}
};
// cin優(yōu)化
static const auto __ = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
這個(gè)題中不得不提一下c++中cin的優(yōu)化問(wèn)題助琐，優(yōu)化代碼如上，主要就是關(guān)閉stdio同步和解除與cout的綁定面氓，這份代碼在LeetCode提交沒優(yōu)化cin之前大概為比20%的提交快兵钮，而開了cin優(yōu)化便幾乎比100%的提交快了...
關(guān)于cin讀取數(shù)據(jù)的問(wèn)題見這篇文章
本作品采用知識(shí)共享署名-非商業(yè)性使用-禁止演繹 4.0 國(guó)際許可協(xié)議進(jìn)行許可。轉(zhuǎn)載請(qǐng)注明: 作者staneyffer舌界，首發(fā)于我的博客掘譬，原文鏈接: https://chengfy.com/post/8
