二叉樹的層序遍歷
- 題目描述
- 題目分析
- 二叉樹的層序遍歷
- 代碼實作
- 總結
題目描述
題目分析
xxxx這道題，題目是“二叉樹的層序遍歷”，首先我們提取一下題目和題目內容的關鍵詞，“二叉樹”、“層序遍歷”、“每一層值分別存盤到一個vector”
（可能不同的人看的著重點不完全相同，我注意到的是以上三個），二叉樹的層序遍歷還是比較好搞的，根據資料結構的基礎知識，只要我們借助一個佇列，利用佇列的“先進先出”的特性，就能夠很好的進行層序遍歷，為了避免部分讀者暫時不會代碼實作，影響后面的問題分析和代碼閱讀，所以我先講解一下如何借助佇列實作二叉樹的層序遍歷
xxxx如果有想對二叉樹有更深更全面的了解和學習的讀者可以打開下面的鏈接學習：二叉樹的深入學習
二叉樹的層序遍歷
首先看一下動圖，了解怎么叫層序遍歷
xxxx層序遍歷需要借助佇列，首先將頭結點入隊，然后出隊訪問出隊的結點，如果該出隊的結點有左孩子則左孩子入隊；如果有右孩子則右孩子入隊，再回圈，出隊得到一個節點，然后訪問出隊的結點，如果該出隊的結點有左孩子則左孩子入隊；如果有右孩子則右孩子入隊……知道佇列為空，則遍歷結束，
代碼實作
//二叉樹結點的定義
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void SequenceTraversal(TreeNode* root)
{
queue<TreeNode*> q;
q.push(root)
while(q.size())
{
TreeNode node = q.front();
VisitNode(node);
q.pop();
if(node->left)
{
q.push(node->left);
}
if(node->right)
{
q.push(node->right);
}
}
}
xxxx明白了如何進行層序遍歷，接下來我們繼續進行本題的題目分析，
xxxx在“二叉樹”、“層序遍歷”、“每一層值分別存盤到一個vector”這三個關鍵詞中，我們已經解決了前兩個關鍵詞了，現在最重要的，也是我做這道題認為最困難的部分就是如何將每一層的資料分別存盤，通過剛剛對層序遍歷的認識，我們發現，他只能單一的存盤資料，但是無法區分某一個屬于第幾層，因此就需要改進一下便于標識資料屬于第幾層，但是大體思路還是利用佇列進行層序遍歷，
xxxx我們發現在層序遍歷的每個回圈中，大體分為兩個部分：1、處理一個結點，2、將被處理的結點的左右孩子入隊
xxxx這就說明，我們在處理完一個結點后，就可以知道該結點有幾個孩子，我們就可以將孩子的個數統計出來，這樣我們處理一個孩子就將計數器-1，直到計數器為0，我么就知道了這個結點的孩子已經處理完成，
xxxx將一個結點擴展成一層結點，假設我們已知某一層有num個結點，由于層序遍歷是一層一層遍歷，于是當我們處理完這一層的num結點，計數器count就可以統計處這一層結點一共有幾個孩子，孩子數量count就是下一層結點的個數，然后我們再把count賦值給num，這樣就更新了下一層的結點個數，count就可以再次統計處下一層結點的孩子個數，這樣一直回圈，還是截止到佇列為空，遍歷結束，這樣我們就能很好的知道每一層的結點個數，
代碼實作
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
if(root == nullptr)
return {};
vector<vector<int> > ret;
queue<TreeNode*> q;
//先將頭結點入隊
q.push(root);
//第一層只有頭結點，所以num初始化為1
int num = 1;
//記錄下一層結點數的計數器count初始化0
int count = 0;
//定義v，用于存盤每一層的結果
vector<int> v;
while(q.size())
{
//先從隊中取出對頭資料
TreeNode* tmp = q.front();
//處理該結點，將val插入到v中
v.push_back(tmp->val);
//pop掉之后count就減1，說明這一層處理完一個資料了
q.pop();
num--;
//如果有左孩子，則入隊
if(tmp->left)
{
q.push(tmp->left);
//count++，證明下一層結點數+1
count++;
}
//如果有右孩子，則入隊
if(tmp->right)
{
q.push(tmp->right);
//count++，證明下一層結點數+1
count++;
}
//因為處理該層一個結點num-1，如果num==0，說明該層結點處理完畢，就要更新num，count
if(num==0)
{
//將該層的結果push到二維陣列中
ret.push_back(v);
vector<int> a;
v = a;
//該處理下一層了，下一層結點數就是count
num = count;
//count重新置為0
count = 0;
}
}
//回圈結束，就可以回傳vector<vector<int>>這個二維陣列了
return ret;
}
};
總結
xxxx這道題考查的本質就是二叉樹的層序遍歷，其實二叉樹的層序遍歷本身不是一個特別難的知識點，只要實作過一次，基本就能很好的實作層序遍歷，所以如果這題，沒有要求分別回傳每一層的資料結果，是不可能到達一個中等難度的，困難點就在于如何控制每一層的開始和停止，如何知道什么時候一層結束，那我們利用的方面有：1、層序遍歷，就是一層一層的遍歷；2、對于每個結點，我們都可以直接訪問他們的左右孩子進行計數，
xxxx這道題大體就是這樣，如果有好的解題方法或者我的方法有什么瑕疵錯誤，請在評論區指出，讓我們互相學習，共同進步，謝謝大家！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298370.html
標籤：其他
下一篇：快速傅里葉變換