Dare2Solve
The problem requires finding the level in a binary tree that has the maximum sum of node values. The binary tree is traversed level by level, and the sum of node values for each level is calculated. The level with the highest sum is returned as the result.
To solve this problem, the key idea is to leverage the level order traversal (breadth-first traversal) of the binary tree. As we traverse each level, we calculate the sum of node values and keep track of the maximum sum encountered. The level corresponding to this maximum sum is the desired output.
Initialization:
sums
to store the sum of node values for each level.Traversal:
sums
list.Compute Maximum:
sums
list.Return the Result:
The algorithm performs a single traversal of the tree, making the time complexity O(N), where N is the number of nodes in the tree.
The space complexity is O(H), where H is the height of the tree, due to the recursive stack or the queue used in level order traversal.
class Solution {
public:
int maxLevelSum(TreeNode* root) {
vector<int> sums;
traverse(root, 0, sums);
return max_element(sums.begin(), sums.end()) - sums.begin() + 1;
}
private:
void traverse(TreeNode* node, int depth, vector<int>& sums) {
if (!node) return;
if (sums.size() == depth) {
sums.push_back(0);
}
sums[depth] += node->val;
traverse(node->left, depth + 1, sums);
traverse(node->right, depth + 1, sums);
}
};
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
sums = []
def traverse(node, depth):
if not node:
return
if len(sums) == depth:
sums.append(0)
sums[depth] += node.val
traverse(node.left, depth + 1)
traverse(node.right, depth + 1)
traverse(root, 0)
return sums.index(max(sums)) + 1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public int maxLevelSum(TreeNode root) {
List<Integer> sums = new ArrayList<>();
traverse(root, 0, sums);
return sums.indexOf(Collections.max(sums)) + 1;
}
private void traverse(TreeNode node, int depth, List<Integer> sums) {
if (node == null) return;
if (depth >= sums.size()) {
sums.add(0);
}
sums.set(depth, sums.get(depth) + node.val);
traverse(node.left, depth + 1, sums);
traverse(node.right, depth + 1, sums);
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var maxLevelSum = function(root) {
const sums = [];
const traverse = (node, depth) => {
if (!node) {
return;
}
sums[depth] = (sums[depth] ?? 0) + node.val;
traverse(node.left, depth + 1);
traverse(node.right, depth + 1);
}
traverse(root, 0);
return sums.findIndex((el) => el === Math.max(...sums)) + 1;
};