1.N叉樹的層序遍歷

我們之前遇到過二叉樹的層序遍歷，只需要用隊列先進先出的特性就可以達到層序遍歷的目的。

而這里不是二叉樹，也就是說讓節點的孩子入隊列時不僅僅是左右孩子了，而是它的所有孩子。而我們看這棵多叉樹的構造，它的孩子是存儲在數組中的。所以我們在讓孩子入隊時只需要依次讓數組中的所有節點入隊列即可。

class Node 
{
public:int val;vector<Node*> children;
}；

而這道題的要求是返回一個二維數組，數組的元素就是每一層的層序遍歷結果。

我們關鍵點就在于如果確定元素屬于那一層，方法就是在進行層序遍歷前，我們先統計該隊列的大小，大小即使這一層元素的個數，當這個數變為0，表示這一層的元素已經統計完了，這時隊列中的就是下一層的元素了。此時重復求大小和層序遍歷的過程即可。

class Solution 
{
public:vector<vector<int>> levelOrder(Node* root) {if(root == nullptr) return {};queue<Node*> q;q.push(root);vector<vector<int>> ret;int currentFloorSize = 0;while(!q.empty()){vector<int> currentFloor;currentFloorSize = q.size();while(currentFloorSize--){Node* head = q.front(); //獲取隊頭元素for(int i=0; i<head->children.size(); ++i) //讓隊頭孩子入隊{q.emplace(head->children[i]);}currentFloor.emplace_back(head->val);//保存隊頭valq.pop();//出隊}ret.emplace_back(currentFloor);}return ret;}
};

2.二叉樹的鋸齒形層序遍歷

依舊是二叉樹的層序遍歷，只不過在遍歷的時候有順序之分，奇數層從左到右，偶數層從右到左。

解法依舊是先采取正常的層序遍歷，多定義一個flag變量用了記錄當前是奇數還是偶數。當把這一行統計完畢后，在將該結果插入到數組之前，先對flag進行判斷，如果是偶數就插入反轉之后的數組，如果奇數則直接插入即可。

class Solution 
{
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(root == nullptr) return {};// 根節點入隊列queue<TreeNode*> q;q.emplace(root);vector<vector<int>> ret;int currentFloorSize =0;int flag = 1; // 遍歷層的方向,奇數層left->right, 偶數層right->leftwhile(!q.empty()){currentFloorSize = q.size();vector<int> currentFloorEele;while(currentFloorSize--){   // 保存節點數據TreeNode* head = q.front();q.pop();currentFloorEele.emplace_back(head->val);// 孩子入隊列if(head->left) q.emplace(head->left);if(head->right) q.emplace(head->right);}if(flag % 2 == 0)reverse(currentFloorEele.begin(), currentFloorEele.end());ret.emplace_back(currentFloorEele);flag++;}return ret;}
};

3.在每個樹行中找最大值

題目要求返回一個數組，數組的元素都是二叉樹每一層的最大值。

解法：我們只需要在進行層序遍歷的過程中，進行最大值的統計即可。當遍歷完該層后，直接保存最大值即可。

class Solution 
{
public:
vector<int> largestValues(TreeNode* root) {if(root == nullptr) return {};queue<TreeNode*> q;q.emplace(root);vector<int> ret;int currentFloorSize = 0;while(!q.empty()){currentFloorSize = q.size();int maxVal = INT_MIN;while(currentFloorSize--){auto head = q.front();q.pop();maxVal = max(maxVal, head->val);if(head->left) q.emplace(head->left);if(head->right) q.emplace(head->right);}ret.emplace_back(maxVal);}return ret;}
};

?4.二叉樹最大深度

返回所有層中最寬的。其中，我們只需要看每一層的最左和最右即可，其中也要計算中間的空節點。

解法：我們將二叉樹以順序方式進行存儲，存儲對用的根節點以及對應的下標。其實就是堆的存儲方式。當我們根節點從0開始，他的左右孩子可以通過2*x+1，2*x+2得來。這樣下來，每一層的寬度其實就是最左與最右節點的下標的差值+1.

class Solution 
{
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*, unsigned int>> LevelSize; // 模擬隊列，將二叉樹以順序結構存儲unsigned int ret = 0; // 統計結果LevelSize.emplace_back(root, 0);while(!LevelSize.empty()){// 取出該層的首尾節點，并更新結果auto& [x1, y1] = LevelSize[0];auto& [x2, y2] = LevelSize.back();ret = max(ret, y2 - y1 + 1);// 讓孩子入隊vector<pair<TreeNode*, unsigned int>> tmp; // 臨時存儲下一層的節點，最后覆蓋原隊列for(auto& [x, y] : LevelSize){if(x->left) tmp.emplace_back(x->left, y * 2 + 1);if(x->right) tmp.emplace_back(x->right, y * 2 + 2);}// 更新層LevelSize = tmp;}return ret;}
};

說明：我們這里使用數組來模擬的隊列，因為我們讓孩子入隊列后得頭刪上一層的元素，在數組中頭刪消耗比較大，所以我們可以用一個臨時數組來統計下一層的元素，之后用臨時數組覆蓋原數組即可。