A Java solution without using a global variable


  • 4
    R

    I am using an array with only one element as a function parameter.

    public class Solution {
        public int maxPathSum(TreeNode root) {
            
            if (root==null) return 0;
            int[] max={Integer.MIN_VALUE};
            maxTree(root,max);
            return max[0];
            
        }
        //@Param:return the sum of the root value and largest branch
        private int maxTree(TreeNode root,int[] max){
            if (root==null) return 0;
            
            int left=root.left!=null?maxTree(root.left,max):Integer.MIN_VALUE;
            int right=root.right!=null?maxTree(root.right,max):Integer.MIN_VALUE;
            
            max[0]=Math.max(max[0],(left>0?left:0)+(right>0?right:0)+root.val);
    
            return root.val+((left>0||right>0)?Math.max(left,right):0);
    
        }
    }

  • 0
    K

    like the trick that use a array as a pointer


  • 0
    A

    Hi Zhang,
    Why do we need to define a global variable to store the result or an array to store the reference of the result? Can't we just use a local variable and pass it as a parameter of the recursive method?
    Thanks


  • 0
    R

    You may take and try and then you would understand why.


Log in to reply
 

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