Given the root
of a binary tree, the level of its root is 1
, the level of its children is 2
, and so on.
Return the smallest level X
such that the sum of all the values of nodes at level X
is maximal.
Example 1:
Input: [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.
Note:
- The number of nodes in the given tree is between
1
and10^4
. -10^5 <= node.val <= 10^5
Solution: HashTable
Use a hash table / array to store the level sum.
Time complexity: O(n)
Space complexity: O(h)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua, 232 ms, 70.2 ms class Solution { public: int maxLevelSum(TreeNode* root) { vector<int> sums; function<void(TreeNode*, int)> preorder = [&](TreeNode* n, int d) { if (!n) return; while (sums.size() <= d) sums.push_back(0); sums[d] += n->val; preorder(n->left, d + 1); preorder(n->right, d + 1); }; preorder(root, 1); int max_sum = sums[1]; int ans = 1; for (int i = 2; i < sums.size(); ++i) if (sums[i] > max_sum) { max_sum = sums[i]; ans = i; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment