How to Get the Maximum Level Sum of a Binary Tree using Breadth
- 时间:2020-09-20 13:49:13
- 分类:网络文摘
- 阅读:101 次
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: 2binary-tree
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 and 10^4.
-10^5 <= node.val <= 10^5
Store the Sum-Level Pairs using C++ Map
The C++ map stores the keys in the ascending order – thus we can store the sum-level pairs and return the last element of the map – which will give us the level for the maximum sum.
When we do the BFS (Breadth First Search) algorithm, we iterate all nodes in the queue – which are of same level, compute the sum, and enqueue the sum-level. If a sum has appeared before, we need to keep the minimum level.
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 26 27 28 29 30 31 32 33 34 35 36 37 38 | /** * 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: int maxLevelSum(TreeNode* root) { queue<TreeNode*> Q; if (root == nullptr) return 0; Q.push(root); int level = 0; map<int, int> sum; while (!Q.empty()) { int cursum = 0; int count = Q.size(); level ++; // expand nodes of same level for (int i = 0; i < count; ++ i) { auto p = Q.front(); cursum += p->val; if (p->left != nullptr) Q.push(p->left); if (p->right != nullptr) Q.push(p->right); Q.pop(); } if (sum.find(cursum) == sum.end()) { sum[cursum] = level; } else { sum[cursum] = min(sum[cursum], level); } } return rbegin(sum)->second; } }; |
/** * 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: int maxLevelSum(TreeNode* root) { queue<TreeNode*> Q; if (root == nullptr) return 0; Q.push(root); int level = 0; map<int, int> sum; while (!Q.empty()) { int cursum = 0; int count = Q.size(); level ++; // expand nodes of same level for (int i = 0; i < count; ++ i) { auto p = Q.front(); cursum += p->val; if (p->left != nullptr) Q.push(p->left); if (p->right != nullptr) Q.push(p->right); Q.pop(); } if (sum.find(cursum) == sum.end()) { sum[cursum] = level; } else { sum[cursum] = min(sum[cursum], level); } } return rbegin(sum)->second; } };
The last element of a C++ std::map can get obtained via the rbegin iterator and the end is actually one element beyond the last – which may return undefined value.
The algorithmic complexity is O(NLogN) where N is the number of the binary trees – as the C++ std::map internally uses a Red/Black tree to maintain the order and it takes O(logN) to find an element.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Awardspace免费php空间稳定可绑域名没有广告500MB空间 一站式商旅及费用管理平台“汇联易”完成3亿元C+轮融资 研究完各路大神,终于知道你做项目失败的原因了 以技术战疫 融云入围"创客北京2020"疫情防控专题赛50强 微信视频号如何注册?微信视频号如何运营吗? 思创客品牌咨询 帮你的品牌牢牢守住市场地位 为什么说餐饮行业也需要微博营销 餐饮020 新开餐厅微信微博营销四段法 如何实现微博的有效营销呢? 微博营销怎么做?看这篇就行了
- 评论列表
-
- 添加评论