Very simple O(n) java code. Around 10 lines of actual code


  • 1
    S
    public class Solution {
        int maxPath = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            myMaxPathSum(root);
            return maxPath;
        }
        
        public int myMaxPathSum(TreeNode root){
            if(root==null) return 0;
            int l = myMaxPathSum(root.left);
            int r = myMaxPathSum(root.right);
            l = l>0 ? l : 0;
            r = r>0 ? r : 0;
            int temp = l + r + root.val;
            if(temp > maxPath) maxPath = temp;
            if(l>r) root.val = l + root.val ;
            else root.val = r + root.val ;
            return root.val;
        }
    }
    

  • 0

    Brilliant solution! I think "if(l>r) root.val = l + root.val ; else root.val = r + root.val ;" can be "root.val = Math.max(l, r) + root.val;" or "root.val += l > r ? l : r;". So that your code can be shorter.


Log in to reply
 

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