429. N 叉樹的層序遍歷

定義一個(gè)隊(duì)列q，將一層的節(jié)點(diǎn)入隊(duì)，并記錄節(jié)點(diǎn)個(gè)數(shù)。根據(jù)節(jié)點(diǎn)的個(gè)數(shù)，出隊(duì)列，并將其孩子入隊(duì)列。出完隊(duì)列，隊(duì)列當(dāng)前剩余節(jié)點(diǎn)的個(gè)數(shù)就是下次出隊(duì)列的次數(shù)。直到隊(duì)列為空

/*
// 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>> re;queue<Node*> q;if(root==nullptr) return re;q.push(root);while(!q.empty()){int sz=q.size();//當(dāng)前層結(jié)點(diǎn)個(gè)數(shù)vector<int>tmp; //存放當(dāng)前層結(jié)點(diǎn)對(duì)應(yīng)的值for(int i=0;i<sz;i++){Node*t=q.front();q.pop();tmp.push_back(t->val);for(Node*child:t->children) //入隊(duì)當(dāng)前節(jié)點(diǎn)孩子vector<Node*> children{if(child!=nullptr) q.push(child);}}re.push_back(tmp);}return re;}
};

662. 二叉樹最大寬度

我們知道二叉樹可以用用數(shù)組表示，定義根節(jié)點(diǎn)下標(biāo)為1，它左孩子下標(biāo)就是2，右孩子3.

所以 父母節(jié)點(diǎn)節(jié)點(diǎn)下標(biāo) i ,左孩子下標(biāo)i*2 右孩子下標(biāo)i*2+1。

1.存入隊(duì)列中的元素類型為pair<TreeNode*,int>，也要把對(duì)應(yīng)節(jié)點(diǎn)的下標(biāo)傳過去。

2.知道隊(duì)列頭節(jié)點(diǎn)的下標(biāo) 尾節(jié)點(diǎn)的下標(biāo) : i尾?- i頭 +1 尾兩節(jié)點(diǎn)的距離就是當(dāng)前層最長的距離?

3.算完當(dāng)前層，再把它們左右孩子入隊(duì)列，直到隊(duì)列為空.

/*** 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) {uint32_t re=0;vector<pair<TreeNode*,uint32_t>> q;q.push_back(make_pair(root,1));while(q.size()){//1.記錄當(dāng)前層的最大寬度auto&[x1,y1]=q[0];auto&[x2,y2]=q.back();uint32_t tmp=y2-y1+1;re=max(re,tmp);//2.更新q隊(duì)列的節(jié)點(diǎn)（換下一層）vector<pair<TreeNode*,uint32_t>> t;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 re;}
};

用數(shù)組模擬隊(duì)列，便于找頭尾節(jié)點(diǎn)。

出隊(duì)父母節(jié)點(diǎn)，入隊(duì)其孩子節(jié)點(diǎn)。不在原數(shù)組q上進(jìn)行，另開數(shù)組t入隊(duì)其孩子節(jié)點(diǎn)。入完后再把存有孩子節(jié)點(diǎn)的數(shù)組t復(fù)制到原數(shù)組q上，減少數(shù)組出隊(duì)列移動(dòng)元素的時(shí)間。

515. 在每個(gè)樹行中找最大值

遍歷每一層，把每一次的最大值找出來

/*** 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> re;if(root==nullptr) return re;queue<TreeNode*> q;q.push(root);while(!q.empty()){int sz=q.size();int tmp=INT_MIN;for(int i=0;i<sz;i++){auto t=q.front();q.pop();tmp=max(tmp,t->val);if(t->left)q.push(t->left);if(t->right)q.push(t->right);}re.push_back(tmp);}return re;}
};