AC java solution - very simple DFS


  • 5
    D
    private int maxPath = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        traverse(root);
        return maxPath;
    }
    
    public int traverse(TreeNode root){
        if(root == null)    return 0;
        
        int left = traverse(root.left) + root.val;
        int right = traverse(root.right) + root.val;
    
        int tmpMax = Math.max(left, Math.max(right, root.val));
        maxPath = Math.max(maxPath, Math.max(tmpMax, left + right - root.val));
        return tmpMax;
    }

  • 0
    V

    This is beautiful.


Log in to reply
 

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