: https://leetcode.com/problems/find-largest-value-in-each-tree-row
: 515. Find Largest Value in Each Tree Row
: 給你一個二元樹，找出每一個 level 最大的元素列表。
: Example 1:
: https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg
: Input: root = [1,3,2,5,3,null,9]
: Output: [1,3,9]
: Example 2:
: Input: root = [1,2,3]
: Output: [1,3]
思路：
跟R大一樣用BFS遍歷，這邊補上C++和Python作法
========== Python Code
from collections import deque
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if (root == None):
return []
queue = deque()
queue.append(root)
ret = []
while(queue):
qsize = len(queue)
maxval = -float('inf')
for i in range(qsize):
node = queue.popleft()
maxval = max(maxval, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ret.append(maxval)
return ret
========== C++ Code
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> q;
vector<int> ret;
if (root == nullptr) return ret;
q.push(root);
while(!q.empty())
{
int qsize = q.size();
int maxval = INT_MIN;
for (int i = 0; i < qsize; ++i)
{
TreeNode* node = q.front();
q.pop();
maxval = max(node->val, maxval);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ret.push_back(maxval);
}
return ret;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.12.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698143396.A.81B.html