木又連續日更第95天（95/100）
木又的第139篇leetcode解題報告
二叉樹
類型第29篇解題報告
leetcode第515題：在每個樹行中找最大值
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
【題目】
您需要在二叉樹的每一行中找到最大的值。
示例：
輸入:
1
/ \
3 2
/ \ \
5 3 9
輸出: [1, 3, 9]
複制
【思路】
本題和【T138-找樹左下角的值】較為類似，同樣有兩種解法：一是層次周遊，得到每一層元素，再找到每一層的最大值；二是中序周遊（前序周遊和後序周遊也可以），存儲節點的值，并标記其層數，當某一層某個節點的值大于存儲的值時，進行替換。
昨天分享的是第二種解法，今天分享第一種解法。
【代碼】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def largestValues(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
# 層次周遊，找到最大值
p = [root]
q = []
res = []
val = root.val
while p or q:
if not p:
p = copy.copy(q)
q = []
res.append(val)
val = p[0].val
cur = p.pop(0)
val = max(val, cur.val)
# 加入下一層節點
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
# 最後一次循環，p、q皆為空
res.append(val)
return res
複制
C++版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
if(!root)
return res;
queue<TreeNode*> p;
queue<TreeNode*> q;
p.push(root);
int val = root->val;
TreeNode* cur = NULL;
while(!p.empty() || !q.empty()){
if(p.empty()){
while(!q.empty()){
p.push(q.front());
q.pop();
}
res.push_back(val);
// 新的一層，改變初始值
val = p.front()->val;
}
cur = p.front();
p.pop();
val = max(val, cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
// 最後一次周遊，p、q都為空，未能添加最後一層的最大元素
res.push_back(val);
return res;
}
};
複制