Accepted short solution in Java


  • 230
    W

    Here's my ideas:

    • A path from start to end, goes up on the tree for 0 or more steps, then goes down for 0 or more steps. Once it goes down, it can't go up. Each path has a highest node, which is also the lowest common ancestor of all other nodes on the path.
    • A recursive method maxPathDown(TreeNode node) (1) computes the maximum path sum with highest node is the input node, update maximum if necessary (2) returns the maximum sum of the path that can be extended to input node's parent.

    Code:

    public class Solution {
        int maxValue;
        
        public int maxPathSum(TreeNode root) {
            maxValue = Integer.MIN_VALUE;
            maxPathDown(root);
            return maxValue;
        }
        
        private int maxPathDown(TreeNode node) {
            if (node == null) return 0;
            int left = Math.max(0, maxPathDown(node.left));
            int right = Math.max(0, maxPathDown(node.right));
            maxValue = Math.max(maxValue, left + right + node.val);
            return Math.max(left, right) + node.val;
        }
    }

  • 0
    R

    almost the same as my answer


  • 0
    C

    Thank you. Nice code, very intuitive!


  • 0
    D

    can anyone explain it in more deep
    How can you find the maximum sum between any two nodes?


  • 3
    R

    for each node, call function once, and this code is right only when each value is positive.
    It update maxvalue for each call, and return one branch maxvalue for its parent node, as return value may combine with other node to ensure path valid


  • 0
    Z

    better than mine


  • 27
    M

    The most tricky point is the global variable maxValue in the following sentence:

    maxValue = Math.max(maxValue, left + right + node.val);
    

    The second maxValue contains the bigger between the left sub-tree and right sub-tree.
    if (left + right + node.val < maxValue ) then the result will not include the parent node which means the maximum path is in the left branch or right branch.


  • 8
    M

    We can give up the member variable by passing it as a parameter to avoid global thing.(CPP)

    int maxPathSum(TreeNode* root) {
        int maxValue = INT_MIN;
        maxPathDown(root, maxValue);
        return maxValue;
    }
    int maxPathDown(TreeNode* node, int &maxValue) {
        if (node == nullptr) return 0;
        int left = max(0, maxPathDown(node->left, maxValue));
        int right = max(0, maxPathDown(node->right, maxValue));
        maxValue = max(maxValue, left + right + node->val);
        return max(left, right) + node->val;
    }

  • 0
    G

    in Python, we can do this like ans = [root.val] ...... def maxPathDown(....., ans): ans[0] = ...


  • 1
    G

    I got the same idea of a global variable, but the prettier thing that @wei-bung had done is when maxPathDown(node.left or node.right) is negative, he change it to zero. Failed coming up with this, I used more if...else... structures.


  • 0
    A

    The code is perfect,I also learned from your code, however it will return Integer.MIN_VALUE if the tree is a null...


  • 0
    R

    just according the problem statement for corner case I think.


  • 26
    H

    My approach to avoid global variable

    public class Solution {
    public int maxPathSum(TreeNode root) {
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        maxPathSum(max, root);
        return max[0];
    }
    private int maxPathSum(int[] max, TreeNode root){
        if(root == null)
            return 0;
        int leftMax =  Math.max(0, maxPathSum(max, root.left));
        int rightMax = Math.max(0, maxPathSum(max, root.right));
        max[0] = Math.max(max[0],  root.val+leftMax+rightMax);
        return root.val+Math.max(leftMax,rightMax);
    }
    

    }


  • 4

    Cool solution! I rewrite it in C++.

    class Solution { 
    public:
        int maxPathSum(TreeNode* root) {
            sum = INT_MIN;
            pathSum(root);
            return sum;
        }
    private:
        int sum;
        int pathSum(TreeNode* node) {
            if (!node) return 0;
            int left = max(0, pathSum(node -> left));
            int right = max(0, pathSum(node -> right));
            sum = max(sum, left + right + node -> val);
            return max(left, right) + node -> val;
        }
    };

  • 0

    Great explanation!


  • 0

    Why do you use a 1-element array instead of just using an integer?


  • 2
    G

    Because we want that variable to be updated by each callee. If you use an integer, the variable in caller will not be updated (since callee only gets a copy of the integer). If you are using C/C++, you can pass by a pointer, but this is Java. And even the Java wrapper class Integer won't work.


  • 0

    Wow, does Java have no elegant way of handling such cases?


  • 0
    T

    I like the use of the global variable, makes things much easier.


  • 2
    A

    Will this work for tree with negative values ?
    e.g. OJ serialized tree ={-8,-2,-1,-4,-5,-3,# }

    In my understanding the answer should be -1 ,however this algo will return -3.
    Please correct me if i am wrong.


Log in to reply
 

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