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: 2

binary-tree How to Get the Maximum Level Sum of a Binary Tree using Breadth First Search Algorithm? algorithms c / c++ programming languages

binary-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) —

推荐阅读:
数学题:用一根20米长的铁丝,围成一个长、宽是整米数的长方形  数学题:有一杯糖水,糖与水的重量比是1:20  奥数题:如果甲先做1小时,然后乙接替甲做1小时  数学题:服装厂的工人每人每天可以生产4件上或7条裤子  数学题:一个长方体长,宽,高都是两位数,并且它们的和是偶数  数学题:若115,200,268被大于1的自然数除  数学题:一只蚂蚁从墙根竖直向上爬到墙头用了4分钟  一位农妇上午挎了一个空篮子笑眯眯地回家  奥数题:秋游时,小红小玲小芳三个好朋友在一个小组一起活动  平年和闰年自测题 
评论列表
添加评论