代码随想录刷题Day33

这次刷题的主题依旧是关于树的层级遍历问题。

在每个树行中找最大值

这道题套用树的层序遍历模板，每一层中找出每一层的最大值。代码如下：

class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> levelQueue;vector<int> ans;TreeNode* tmp;int cnt = 0;int max = -214748347;//空树if(!root) return ans;levelQueue.push(root);//第一次写代码把这一行代码漏掉，结果导致返回的都是空列表while(!levelQueue.empty()){cnt = levelQueue.size();max = -2147483648;while(cnt--){   //每一层节点取出tmp = levelQueue.front();levelQueue.pop();if(tmp->val > max) max = tmp->val;  //值和当前的最大值比较if(tmp->left) levelQueue.push(tmp->left);   //下一层节点入队if(tmp->right) levelQueue.push(tmp->right);}ans.push_back(max);}return ans;}
};

填充每个节点的下一个右侧节点指针

这道题是在树的纵向结构的基础上，添加横向的指针连接起来，如果想到使用层级遍历的话，这道题思路可以很快有。填充每个节点的下一个右侧节点指针II这道题也可以使用树的层级遍历方法求解：

class Solution {
public:Node* connect(Node* root) {queue<Node*> levelQueue;if(!root) return root;levelQueue.push(root);int cnt = 1;Node* tmp;while(!levelQueue.empty()){cnt = levelQueue.size();while(cnt--){tmp = levelQueue.front();levelQueue.pop();if(tmp->left) levelQueue.push(tmp->left);if(tmp->right) levelQueue.push(tmp->right);if(cnt > 0){tmp->next = levelQueue.front(); //为每一层的非最后一个节点指定next节点}}}return root;}
};

二叉树的最大深度

这道求树的深度，可以是用深度优先搜索，也可以用广度优先搜索，既然这是在树的层序遍历系列题目下，这里就使用树的层序遍历，在逐层遍历的同时，对遍历了多少层进行一个计数：

class Solution {
public:int maxDepth(TreeNode* root) {if(!root) return 0;queue<TreeNode*> levelQueue;levelQueue.push(root);int queue_cnt = 1;int level_cnt = 0;TreeNode* tmp ;while(!levelQueue.empty()){level_cnt++;queue_cnt = levelQueue.size();while(queue_cnt--){tmp = levelQueue.front();levelQueue.pop();if(tmp->left) levelQueue.push(tmp->left);if(tmp->right) levelQueue.push(tmp->right);}}return level_cnt;}
};

二叉树的最小深度

这道题继续使用层级遍历的方法，逐层遍历树，直到在某一层遇到第一个叶子节点就停止继续遍历，其中叶子节点的特点是左孩子和右孩子均为空。代码如下：

class Solution {
public:int minDepth(TreeNode* root) {if(!root) return 0;queue<TreeNode*> levelQueue;int queue_cnt = 1;int min_level_cnt = 0;bool min_find = false;levelQueue.push(root);TreeNode* tmp;while(!levelQueue.empty()){queue_cnt = levelQueue.size();min_level_cnt ++;   //下一层的节点遍历while(queue_cnt --){//挨个取这一层的节点tmp = levelQueue.front();levelQueue.pop();if(!tmp->left && !tmp->right){//在这一层遇到一个叶子节点，即可结束遍历过程min_find = true;break;}else{//如果没有叶子节点，则继续把下一层节点入队if(tmp->left) levelQueue.push(tmp->left);if(tmp->right) levelQueue.push(tmp->right);}}if(min_find) break; //找到叶子节点，无需继续遍历下去}return min_level_cnt;}
};

层序遍历小结

对于使用这一类解法，典型的特点是处理的内容和每一层有很强的关联，比如

• 直接求层序遍历结果
• 或者是求每一层的相关属性，如求右视图是在求每一层的最右节点，求每一层的平均值，或者是最大值，或者是在每一层中添加横向的next指针
• 或者是关于树深度的一些性质，由于树的层序遍历时一层一层的遍历，所以，树的深度也是可以在一层层扫描中获得。

整体写代码的思路框架是：

• root是否为空指针的判断（这几乎成为大部分处理树的问题的第一步操作）
• 如果root非空
  • 外层循环用于逐层遍历。使用一个队列levelQueue记录每一层的节点，cnt在每一层的节点遍历之前记下队列中元素的个数，也是这一层的节点数目，用于控制队列元素出队的次数
    • 外层循环可以用于处理比如关于深度计算的问题。
  • 内层循环用于每一层中的元素遍历。从队列中依次出队cnt个元素，并把这cnt个元素的left（如果非空）和rigth（如果非空）加入队列，作为下一层要遍历的元素。
    • 在这一个内层循环里，可以执行关于树的层级相关操作，比如print元素（层序遍历结果的返回）、计算平均值、求最大值、求最右节点、层内结点横向连接等。
  • 如此执行外层循环，直到队列为空，也就是下一层没有元素要遍历为止。
• 最后返回满足要求的答案值。