[LeetCode] Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

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: DFS.
This is one of those classic problems for which a not-careful-enough implementation would take O(n*H) time, where n is the total number of nodes in the tree, and H is the height of the tree. And H can be as good as O(log n), and as bad as O(n). Such an implementation has duplicate computations.
An optimal solution should make sure that we do not compute the same thing twice. A typical way to do so is to compute two different things at the same time. In the following code, we are computing the max prefix sum starting from root and the max path sum through root at the same time (in one function).
Time Complexity: O(n), where n is the total number of nodes in the tree.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

/** * 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; private int maxPrefixSum(TreeNode root) { if (root == null) { return 0; } int left_max_preSum = maxPrefixSum(root.left); int right_max_preSum = maxPrefixSum(root.right); // Compute the max path sum through root int max_through_here = root.val; if (left_max_preSum > 0) { max_through_here += left_max_preSum; } if (right_max_preSum > 0) { max_through_here += right_max_preSum; } if (maxSum < max_through_here) { maxSum = max_through_here; } // Compute the max prefix sum starting from root int max_preSum_root = root.val; int max_preSum_subtree = Math.max( left_max_preSum, right_max_preSum ); if (max_preSum_subtree > 0) { max_preSum_root += max_preSum_subtree; } return max_preSum_root; } public int maxPathSum(TreeNode root) { maxSum = Integer.MIN_VALUE; maxPrefixSum(root); return maxSum; } }