124. Binary Tree Maximum Path Sum
Last updated
Last updated
// 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);
}
}