Binary Tree Maximum Path Sum
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.
Examples
Constraints
The number of nodes in the tree is in the range [1, 3 * 10^4].-1000 <= Node.val <= 1000
Bottom-up DFS
Approach
A path going through a node can include its left child path, right child path, or both (if it's the highest point of the arch). We use a recursive function that returns the maximum path sum going down from the current node (either left or right, but not both). However, while at the current node, we also calculate the sum of the path that arcs through it (`node.val + leftPath + rightPath`) and update our global max if it's larger. If a child path sum is negative, we ignore it by taking `max(0, path)`.
Complexity Analysis
This optimally computes the path sum in a single pass of the tree.
class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return maxSum; } // Returns max path sum without splitting (can only go down one branch) private int dfs(TreeNode node) { if (node == null) return 0; // Ignore negative paths int leftMax = Math.max(0, dfs(node.left)); int rightMax = Math.max(0, dfs(node.right)); // Calculate max path passing through this node (splitting) maxSum = Math.max(maxSum, node.val + leftMax + rightMax); // Return max path sum without splitting return node.val + Math.max(leftMax, rightMax); }}