题目描述
给你一个二叉树的根结点 root
。设根结点位于二叉树的第 1
层,而根结点的子结点位于第 2
层,依此类推。
请你找出层内元素之和 最大 的那几层(可能只有一层)的层号,并返回其中 最小 的那个。
样例
输入:[1,7,0,7,-8,null,null]
输出:2
解释:
第 1 层各元素之和为 1,
第 2 层各元素之和为 7 + 0 = 7,
第 3 层各元素之和为 7 + -8 = -1,
所以我们返回第 2 层的层号,它的层内元素之和最大。
提示
- 树中的结点数介于
1
和10^4
之间。 -10^5 <= node.val <= 10^5
算法
(递归遍历) $O(n)$
- 采用先序遍历,递归中传递记录每一层累加和的数组
level
。 - 如果当前层还没有创建,则在数组末尾新增添一个元素。
- 遍历结束后找答案即可。
时间复杂度
- 每个结点遍历一次,故时间复杂度为 $O(n)$。
空间复杂度
- 递归需要系统栈空间,
level
需要 $O(h)$ 的空间,其中 $h$ 为树的最大高度,故空间复杂度为 $O(h)$。
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:
void solve(TreeNode* rt, vector<int> &level, int dep) {
if (rt == NULL)
return;
if (dep >= level.size())
level.push_back(0);
level[dep] += rt -> val;
solve(rt -> left, level, dep + 1);
solve(rt -> right, level, dep + 1);
}
int maxLevelSum(TreeNode* root) {
vector<int> level;
solve(root, level, 0);
int ans = INT_MIN, ans_level = -1;
for (int i = 0; i < level.size(); i++)
if (level[i] > ans) {
ans = level[i];
ans_level = i;
}
return ans_level + 1;
}
};