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(http://www.reibang.com/p/814d871c5f6d)的思路基本相同.即層遍歷二叉樹,然后在每層中分別找最大的.
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> q; //結(jié)點(diǎn)隊(duì)列
vector<int> res; //輸出
if (!root) return res; //若root為空,直接返回
q.push(root);
while(!q.empty()) {
int size = q.size(); //記錄此時(shí)刻隊(duì)列大小(層大小)
int max = q.front()->val; //先假設(shè)最大值結(jié)點(diǎn)是隊(duì)列頭(很重要,不能一上來就假設(shè)max初始為0這種不嚴(yán)謹(jǐn)?shù)膶懛?
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;
}
