1 题目描述
题目链接：在每个树行中找最大值
2 题目解析
根据题目描述，是找出每一行中的最大值，这毋庸置疑是使用宽度优先遍历了。我在这篇文章中讲解了宽度优先遍历的模板，如果没有看的同学可以先去看一下。
这道题和模板的不同之处在于，需要计算出每一行中的最大值。因此，可以有下面两个思路：
1. 模板中已经拿到了全部的节点值，每一行在vector< int >中，因此可以对每个vector< int >遍历一遍，求出每一行的最大值
2. 在遍历树的过程中出现过对树的每一行都进行遍历的过程，因此可以在遍历树的每一行时找出最大的值
3 代码
3.1 思路1代码
class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;queue<TreeNode*> q;if (root == nullptr)return ret;q.push(root);while(q.size()){int m = INT_MIN;//存储的是每一层的值vector<int> tmp;//对于每一层 --> 也可以在这一层里面直接计算出maxint sz = q.size();for (int i = 0; i < sz; ++ i){TreeNode* t = q.front();tmp.push_back(t->val);if (t->left)q.push(t->left);if (t->right)q.push(t->right);q.pop();}//找出这一层中最大的值for (int i = 0; i < tmp.size(); ++ i){m = max(m, tmp[i]);}ret.push_back(m);}return ret;}
};
3.2 思路2代码
class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> res;queue<TreeNode*> q;if (root == nullptr)return res;q.push(root);while(q.size()){int sz = q.size();int m = INT_MIN; //这里m不能为0，因为最小值是-2的31次方//vector<int> tmp;for (int i = 0; i < sz; ++ i){TreeNode* t = q.front();q.pop();m = max(m, t->val);if (t->left)q.push(t->left);if (t->right)q.push(t->right);}res.push_back(m);}return res;}
};
