2m easy understand Java solution with explanation

  • 2

    There are 4 possible results:

    1. root.val
    2. root.val + max sum of left branch // left fork
    3. root.val + max sum of right branch // right fork
    4. root.val + max sum of left branch + max sum of right branch // the arch

    The final result is the max of these 4

       public static int maxPathSum(TreeNode root) {
            if (root == null) return 0;
            int[] res = new int[1];
            res[0] = root.val;
            maxBranchSum(root, res);
            return res[0];
        public static int maxBranchSum(TreeNode root, int[] res) {
            if (root == null) return 0;
            int leftB = maxBranchSum(root.left, res);      // left fork without root
            int rightB = maxBranchSum(root.right, res);  // right fork without root
            int maxB = root.val + Math.max(leftB, rightB); 
            maxB = Math.max(root.val, maxB);               // max fork with root
            int maxPath = Math.max(maxB, root.val + leftB + rightB);   // max between max fork and the  arch
            res[0] = Math.max(res[0], maxPath); // update the final result
            return maxB;

  • 0

    I have some questions about your solution.

    1. Why would you use an array res[] with only one value, instead of just using int res?

    2. As you said, the final result is the max of these 4, but when I tried maxB = Math.max(maxB, root.val + leftB + rightB); and res = Math.max(res, maxB) and return maxB without using maxPath, I got an error. So why can't this work?

  • 1

    1、 Because res[] is mutable while int res is not.
    2、 Did you compare maxB and root.val? Because root.val is possible larger than root.val + leftB + rightB

  • 0

    @he.jeffery Thank you for the explanation.

Log in to reply

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