Binary Tree Maximum Path Sum | Leetcode

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

---

Solution: Recurse through the tree, keeping track of the maximum path sum ever found. For each node, we can compute the max by considering branching out to both left and right sub-trees. But to return the max sum for the current node, we can only take one path, either the node itself only, or the node + the left sub-tree, or the node + the right sub-tree. Return the maximum path sum ever found as the answer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum;
    
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        maxSum = root.val;
        recurse(root);
        return maxSum;
    }
    
    private int recurse(TreeNode node) {
        if (node == null) return 0;
        
        int left = recurse(node.left);
        int right = recurse(node.right);
        
        // For the current node, pick only a single path.
        int current = Math.max(node.val, Math.max(node.val + left, node.val + right));
        
        // For maxSum, we can pick two paths both branching out from node.
        maxSum = Math.max(maxSum, Math.max(current, node.val + left + right));
        
        return current;
    }
}