題目描述
- 給你二叉樹(shù)的根節(jié)點(diǎn)
root，返回其節(jié)點(diǎn)值的 層序遍歷 。 （即逐層地，從左到右訪(fǎng)問(wèn)所有節(jié)點(diǎn)）。
示例1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]
示例 2：
輸入：root = [1]
輸出：[[1]]
示例 3：
輸入：root = []
輸出：[]
提示：
- 樹(shù)中節(jié)點(diǎn)數(shù)目在范圍
[0, 2000]內(nèi) -1000 <= Node.val <= 1000
思路分析
這個(gè)問(wèn)題實(shí)際上可以只用一個(gè)隊(duì)列就實(shí)現(xiàn)，只需要再增加一個(gè)變量levelSize，用來(lái)記錄每一層的數(shù)據(jù)個(gè)數(shù)，然后再讓這個(gè)隊(duì)列一層一層的出去。之前的方法中，實(shí)際上隊(duì)列并不是一層一層出去的，它有可能隊(duì)列里面同時(shí)有兩層的數(shù)據(jù)，我們以下面這個(gè)圖來(lái)解釋一下原因：
如果有兩層隊(duì)列實(shí)現(xiàn)的話(huà)，3這個(gè)節(jié)點(diǎn)出來(lái)的時(shí)候，會(huì)讓9和20這兩個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列，而9這個(gè)節(jié)點(diǎn)出來(lái)的時(shí)候會(huì)讓15這個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列，這個(gè)時(shí)候隊(duì)列里面就同時(shí)有了第2層和第3層的數(shù)據(jù)。
所以我們想通過(guò)levelSize來(lái)達(dá)到一個(gè)目的：控制這個(gè)隊(duì)列實(shí)現(xiàn)一層一層的出去。
那我們要怎么實(shí)現(xiàn)呢？我們?nèi)匀灰詣偛诺膱D來(lái)進(jìn)行分析：
3節(jié)點(diǎn)進(jìn)入隊(duì)列的時(shí)候，它的層數(shù)為1，由于它是根節(jié)點(diǎn)，所以它肯定只有一個(gè)，所以3就可以直接出隊(duì)列。這個(gè)時(shí)候我們讓levelSize進(jìn)行自減操作它就變成了0，表示這一層已經(jīng)出完了。
那么由于3節(jié)點(diǎn)出的時(shí)候會(huì)把9和20也帶進(jìn)來(lái)，也就是說(shuō)當(dāng)前層的節(jié)點(diǎn)全部出隊(duì)列的時(shí)候一定是下一層的節(jié)點(diǎn)全部進(jìn)入隊(duì)列，這個(gè)時(shí)候我們將levelSize重新更新為第二層節(jié)點(diǎn)的數(shù)目也就是2，然后再進(jìn)行出隊(duì)列的操作：9節(jié)點(diǎn)出隊(duì)列同時(shí)將15節(jié)點(diǎn)帶進(jìn)隊(duì)列，然后levelSize自減變?yōu)?code>1；20節(jié)點(diǎn)出隊(duì)列同時(shí)將15節(jié)點(diǎn)和7節(jié)點(diǎn)帶進(jìn)隊(duì)列，levelSize再自減變?yōu)?code>0。這個(gè)時(shí)候就說(shuō)明第二層也出完了。那么此時(shí)第三層都在隊(duì)列里面所以我們?cè)俅胃?code>levelSize的值為3，依次類(lèi)推直到整棵樹(shù)都被遍歷完就實(shí)現(xiàn)了只用一個(gè)隊(duì)列實(shí)現(xiàn)層序遍歷。
那么根據(jù)以上的思路，我們就可以寫(xiě)出下面的代碼：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-838606.html
完整代碼
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
int levelSize = 0;
if (root)//如果根不為空，就入隊(duì)列
{
q.push(root);
levelSize = 1;
}
vector<vector<int>> vv;//用來(lái)存放一層一層出的節(jié)點(diǎn)
while (!q.empty())//如果隊(duì)列不等于空，就說(shuō)明樹(shù)還沒(méi)有被遍歷完
{
//通過(guò)levelSize控制一層一層出
vector<int> v;//用來(lái)存放每一層的數(shù)據(jù)
while (levelSize--)//levelSize是幾循環(huán)就執(zhí)行幾次，--levelSize表示的則是執(zhí)行（levelSize - 1）次
{
TreeNode* front = q.front();//先取隊(duì)頭的數(shù)據(jù)
q.pop();
v.push_back(front->val);
//進(jìn)去的同時(shí)把該節(jié)點(diǎn)的下一層往隊(duì)列里面帶
if (front->left)//左如果不為空就讓左入隊(duì)列
q.push(front->left);
if (front->right)//右如果不為空就讓右入隊(duì)列
q.push(front->right);
}
//走到這里就說(shuō)明當(dāng)前層已經(jīng)出完了，就把當(dāng)前層所出的數(shù)據(jù)放到vv里面
vv.push_back(v);
//更新下一層的數(shù)據(jù)
levelSize = q.size();
}
return vv;
}
};
運(yùn)行結(jié)果
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-838606.html
到了這里，關(guān)于【C++】102.二叉樹(shù)的層序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
