💁♂️个人主页：进击的荆棘
👇作者其它专栏：
《数据结构与算法》《算法》《C++起始之路》
相关题解
1.N 叉树的层序遍历
算法思路：
层序遍历即可，仅需多加一个变量，用来记录每一层节点的个数。
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> ret; if(!root) return ret; queue<Node*> q; q.push(root); int n=0;//存当前队列中有多少数据（即每一层有多少数据） while(!q.empty()){ vector<int> t; n=q.size(); while(n--){//压入当前层的数据 t.push_back(q.front()->val); //将下层节点存入队列中 for(int i=0;i<q.front()->children.size();i++){ q.push(q.front()->children[i]); } q.pop(); } ret.push_back(t); } return ret; } };2.二叉树的锯齿形层序遍历
算法思路：
在正常的层序遍历过程中，可以把一层的节点放在一个数组中，有了这个数组后，在合适的层数逆序就可以得到锯齿形层序遍历的结果。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: //可以观察到奇数层正序，偶数层逆序 vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ret; if(!root) return ret; queue<TreeNode*> q; int n=0; q.push(root); int flag=1; while(!q.empty()){ vector<int> t; n=q.size(); while(n--){ t.push_back(q.front()->val); if(q.front()->left) q.push(q.front()->left); if(q.front()->right) q.push(q.front()->right); q.pop(); } //判断是否逆序 if(flag%2==0) reverse(t.begin(),t.end()); ret.push_back(t); flag++; } return ret; } };3.二叉树最大宽度
算法思路一（会超过内存限制）：
既然统计每一层的最大宽度，优先想到的就是利用层序遍历，把当前层的节点全部存在队列里，利用队列的长度来计算每一层的宽度，统计出最大的宽度。
但是，由于空节点也是需要计算在内的。因此，可以选择将空节点也存在队列里。
但是极端情况下，最左边一条长链，最右边一条长链，会超出最大内存限制。
算法思路二：（利用二叉树的顺序存储，通过根节点的下标，计算左右孩子的下标）：
还是利用层序遍历，但是这一次队列里面不只是存节点信息，并且还存储当前节点对应存在数组中的下标（用数组实现堆时，计算左右孩子的方式）。
这样计算每一层宽度时，无需考虑空节点，只需将当前节点的左右节点的下标相减在加1即可。
细节：若二叉树的层数非常恐怖的话，任何一种数据类型都不能存下下标的值。但是没有问题，因为：
●数据的存储是一个环形的结构；
●且题目说明，数据的范围在int类型的最大值的范围之内，因此不会超出一圈；
●因此，若是求差值，无需考虑溢出的情况。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: //思考用数组模拟堆时的下标之间的关系 int widthOfBinaryTree(TreeNode* root) { vector<pair<TreeNode*,unsigned int>> q;//用数组模拟队列 q.push_back({root,1}); unsigned int ret=1; while(q.size()){ auto& [x1,y1]=q[0]; auto& [x2,y2]=q.back(); ret=max(ret,y2-y1+1); //模拟队列进队 vector<pair<TreeNode*,unsigned int>> t;//频繁在q头删除元素，时间消耗大，可以用一个数组直接覆盖 for(auto& [x,y]:q){ if(x->left) t.push_back({x->left,y*2}); if(x->right) t.push_back({x->right,y*2+1}); } q=t; } return ret; } };4.在每个树行中找最大值
算法思路：
层序遍历过程中，在执行让下一层节点入队时，可以在循环中统计出当前层节点的最大值。
因此，可以在bfs的过程中，统计出每一层节点的最大值。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> largestValues(TreeNode* root) { vector<int> ret; if(!root) return ret; queue<TreeNode*> q; q.push(root); int n=0; while(q.size()){ n=q.size(); int t=INT_MIN; while(n--){ if(q.front()->left) { q.push(q.front()->left); } if(q.front()->right) { q.push(q.front()->right); } t=max(q.front()->val,t); q.pop(); } ret.push_back(t); } return ret; } };
