Back to DSA

Binary Tree Maximum Path Sum

hard
Acceptance: 37%
Binary Tree

In a binary tree, a path is any sequence of connected nodes traveling parent-child edges, where no node appears more than once. The path need not include the root. Compute the highest possible sum of node values along any such path in the tree.

Examples

Example 1:
Input:root = [2,1,4]
Output:7
Explanation: The path 1 -> 2 -> 4 yields the maximum sum of 7.
Example 2:
Input:root = [-5,8,12,null,null,10,3]
Output:25
Explanation: The path 10 -> 12 -> 3 sums to 25.

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order Traversalmedium
00:00
class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));
        maxSum = Math.max(maxSum, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}
Time complexityO(n)
Space complexityO(h)