124. Binary Tree Maximum Path Sum
Description
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Constraints
Approach
Links
YouTube
Examples
Input: [1, 2, 3]
Output: 6
Explanation:
Input: [-10, 9, 20, null, null, 15, 7]
Output: 42
Explanation:
Solutions
// 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;
}
}/**
* Time complexity : O(N), where N is number of nodes, since we visit each
* node not more than 2 times.
* Space complexity : O(H), where H is a tree height, to keep the recursion stack.
* In the average case of balanced tree, the tree height H = logN,
* in the worst case of skewed tree, H = N.
*/
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return maxSum;
}
private int helper(TreeNode node) {
if(node == null) return 0;
int leftSum = Math.max(helper(node.left), 0);
int rightSum = Math.max(helper(node.right), 0);
int sum = leftSum + node.val + rightSum;
maxSum = Math.max(maxSum, sum);
return node.val + Math.max(leftSum, rightSum);
}
}Follow up
Last updated
Was this helpful?