Accepted solution in Java


  • 2
    E

    The idea here is that using recursion, get the max of the left and right child, and add that to the current node value. If the child returns a negative sum, disregard that child in the new sum. You check the sum of current node value + (max from left child) + (max from right child) and replace the global max variable if it is greater.

    public class Solution {
        
        public int max = 0;
        
        public int maxPathSum(TreeNode root) {
            if (root == null) {
                return 0;
            }
            max = root.val;
            maxPathSumHelper(root);
            return max;
        }
        
        public int maxPathSumHelper(TreeNode root) {
            int left = 0, right = 0;
            if (root.left != null) {
                left = maxPathSumHelper(root.left);
            }
            if (root.right != null) {
                right = maxPathSumHelper(root.right);
            }
            left = left > 0 ? left : 0;
            right = right > 0 ? right : 0;
            if (root.val + left + right > max) {
                max = root.val + left + right;
            }
            return root.val + Math.max(left, right);
        }
    }

  • 0

    Nice and clean code. well done!


Log in to reply
 

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