Every day a Leetcode
题目来源:1161. 最大层内元素和
解法1:层序遍历
每次以「层」为单位进行拓展,统计该层的元素和,维护处理过程中的最大值层数和,以及层深度。
代码:
/*
* @lc app=leetcode.cn id=1161 lang=cpp
*
* [1161] 最大层内元素和
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
int maxLevelSum(TreeNode *root)
{
if (root == nullptr)
return 0;
int ans = 0;
int curLevel = 0;
int maxLevelSum = INT_MIN;
queue<TreeNode *> q;
q.push(root);
while (!q.empty())
{
curLevel++;
int sz = q.size();
int levelSum = 0;
for (int i = 0; i < sz; i++)
{
auto node = q.front();
q.pop();
levelSum += node->val;
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
if (levelSum > maxLevelSum)
{
maxLevelSum = levelSum;
ans = curLevel;
}
}
return ans;
}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n),其中 n 是二叉树的节点个数。
空间复杂度:O(n),其中 n 是二叉树的节点个数。