Trees - Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can appear at most once. Given a binary tree, return the maximum path sum of any non-empty path.

Input: root=[1,2,3] → Output: 6

Input: root=[-10,9,20,null,null,15,7] → Output: 42

DFS: at each node, compute the max gain from left and right subtrees (only positive contributions count). Update global max with left_gain + root.val + right_gain. Return max single-branch gain to parent.

Global maxSum = Integer.MIN_VALUE.
dfs(node): if null return 0.
leftGain = max(0, dfs(left)), rightGain = max(0, dfs(right)).
Update maxSum = max(maxSum, node.val + leftGain + rightGain).
Return node.val + max(leftGain, rightGain).

class Solution { 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, node.val + left + right); return node.val + Math.max(left, right); } }

Time Complexity: O(N)
Space Complexity: O(H)