Leetcode
Problem description:
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Solution with javascript
Here is a possible solution to the problem using JavaScript, taking into account that the problem statement allows for non-consecutive nodes in the path:
function maxPathSum(root) {
let maxSum = Number.MIN_SAFE_INTEGER;
function dfs(node) {
if (!node) return 0;
let left = Math.max(0, dfs(node.left));
let right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, left + right + node.val);
return Math.max(left, right) + node.val;
}
dfs(root);
return maxSum;
}
In this solution, the dfs
function returns the maximum path sum that ends at the current node. It calculates this sum by taking the maximum of the left and right sub-paths that originate from the current node, and adding the value of the current node to this maximum. This sum is then used by the parent node to calculate its own path sum.
Additionally, dfs
also updates maxSum
with the maximum path sum found so far, which includes the current node and both of its sub-paths. This ensures that the maximum path sum is correctly calculated even when the path does not pass through the root node.
Here is a brief description of the steps the code takes:
Define a function
maxPathSum
that takes a root node of a binary tree as its argument. Initialize a variablemaxSum
with the smallest possible integer value.Define a helper function
dfs
that takes a node as its argument. This function will be used to traverse the tree and calculate the maximum path sum that ends at the current node.Inside
dfs
, check if the current node is null. If it is, return 0 from the function.Call
dfs
recursively on the left and right child nodes of the current node and store the returned values in left and right.Set left and right to 0 if they are negative, using the Math.max function. This ensures that only positive sub-path sums are considered when calculating the maximum path sum for the current node.
Update
maxSum
with the maximum of the current value and the sum of the left sub-path, the right sub-path, and the value of the current node. This calculates the maximum path sum that includes the current node and both of its sub-paths.Return the maximum of the left and right sub-paths plus the value of the current node. This calculates the maximum path sum that ends at the current node and can be used by the parent node to calculate its own path sum.
At the end of
maxPathSum
, calldfs
on the root node to start the traversal of the tree and the calculation of the maximum path sum.Return
maxSum
as the result ofmaxPathSum
.
This solution assumes that the binary tree is represented using node objects with left and right properties that refer to the left and right child nodes, and a val property that holds the value of the node. It also assumes that the tree does not contain any null nodes, i.e., all non-leaf nodes have both
Thanks for reading! share if you find it helpful.
Top comments (0)