Calculating Sum on the Longest Root-to-Leaf Path
Fri Mar 22 2024 maxHeightSum:
A method meticulously crafted to traverse the tree, keeping a tally of both the length and sum of the path from the root to each leaf. By recursively exploring every possible path, it updates a global tally to reflect the maximum sum encountered on the longest path. Should multiple paths of the same length emerge, the method adeptly ensures that the path with the greatest sum is the one considered. This dual-focus approach on length and sum unveils the path that is not just the longest but also the most "valuable" in terms of node summation.
1class Node {
2 constructor(val) {
3 this.data = val;
4 this.left = null;
5 this.right = null;
6 }
7}
8
9const one = new Node(1);
10const two = new Node(2);
11const three = new Node(3);
12const four = new Node(4);
13const five = new Node(5);
14const six = new Node(6);
15const seven = new Node(7);
16const eight = new Node(8);
17
18one.left = two;
19one.right = three;
20two.right = five;
21two.left = four;
22five.right = seven;
23five.left = six;
24seven.left = eight;
25
26function maxHeightSum(root) {
27 let maxSum = -Infinity;
28 let maxLength = 0;
29 if (!root) return 0;
30 function sumLongestPath(root, sum, len) {
31 if (!root) {
32 if (maxLength < len) {
33 maxLength = len;
34 maxSum = sum;
35 } else if (maxLength === len && maxSum < sum) {
36 maxSum = sum;
37 }
38 return;
39 }
40 sumLongestPath(root.left, sum + root.data, len + 1);
41 sumLongestPath(root.right, sum + root.data, len + 1);
42 }
43 sumLongestPath(root, 0, 0);
44 return maxSum;
45}
46
47console.log(maxHeightSum(one));
48