You need to find the largest value in each row of a binary tree.
Example:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: [1, 3, 9]
思路:和637. Average of Levels in Binary Tree(https://www.jianshu.com/p/814d871c5f6d)的思路基本相同.即层遍历二叉树,然后在每层中分别找最大的.
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> q; //结点队列
vector<int> res; //输出
if (!root) return res; //若root为空,直接返回
q.push(root);
while(!q.empty()) {
int size = q.size(); //记录此时刻队列大小(层大小)
int max = q.front()->val; //先假设最大值结点是队列头(很重要,不能一上来就假设max初始为0这种不严谨的写法)
for (int i = 0; i < size; i++) { //遍历该层,找最大值
TreeNode* tmp = q.front();
q.pop();
if (tmp->val > max) max = tmp->val;
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
}
res.push_back(max);
}
return res;
}
