Short and fast, easy to understand Java code


  • 2

    Idea: the search function takes in a node as a parameter, and returns the length of the path that comes from either its left or right child, which can further grow to the parent node. While always returning the partial path length to the upper layer, the length of the path that contains nodes from both its left and right subtrees are also calculated to be a potential candidate result.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int maxPathSum(TreeNode root) {
            this.max = Integer.MIN_VALUE;
            
            search(root);
            
            return max;
        }
        
        int search(TreeNode node) {
            if (node == null) return 0;
            
            int leftResult = search(node.left);
            int rightResult = search(node.right);
            
            int result = Math.max(Math.max(leftResult, rightResult) + node.val, node.val);
            
            max = Math.max(Math.max(leftResult + rightResult + node.val, result), max);
            
            return result;
        }
        
        private int max;
    }
    

Log in to reply
 

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