Elegant Java solution

  • 69
    public class Solution {
        int max = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            return max;
        // helper returns the max branch 
        // plus current node's value
        int helper(TreeNode root) {
            if (root == null) return 0;
            int left = Math.max(helper(root.left), 0);
            int right = Math.max(helper(root.right), 0);
            max = Math.max(max, root.val + left + right);
            return root.val + Math.max(left, right);

  • 1

    the val of node may be negative, the code upside presume all val of node is bigger than 0

  • 3

    @nanitou You didn't capture the key idea of this code. The author deals the negative with max(helper(root.left), 0) this max comparison.

  • 0

    This one is the best!

  • 9

    The basic idea is to traversal every nodes as the top of sub tree and calculate left max and right max individually, then keep update max. The most elegant point is that you did both in one method, implemented it by not only return but also keeping updating max as a field.

  • 0

    I had the same idea as you, but I implemented the traversal iteratively using a stack and implemented calculating left branch max and right branch max recusively. It ended up with a TLE.

  • 1

    @jeantimex : i understood your logic . I have few questions regarding your code :
    max = Math.max(max, root.val + left + right); -- > This line of code compares the max value from every iteration with the current sum and updates it .
    root.val + Math.max(left, right) -- > what is the purpose of this code ? is it for computing the values level up the top node and computing it with its root node ? is this value be returned to helper(node.left) or helper(node.right) in choosing the maximum value?

  • 1

    Hi @d20@15, you can imagine the helper( ) function goes from the bottom of the tree to the top, it's in post-order manner.

    At every node, we need to make a decision, if the sum comes from the left path larger than the right path, we pick the left path and plus the current node's value, this recursion goes all the way up to the root node.

  • 0

    @jeantimex : Thank you so much ! it is pretty much clear now !

  • 1

    the key point is replacing the negative max value and null nodes value with 0, thus there would no negative value in any binary tree, and we need not care about any single node.

                                     /      \   
                      left max value        right max value

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.