<124> Binary Tree Maximum Path Sum

Posted on Edited on In Views:

Description

Question: Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Leetcode link: 124. Binary Tree Maximum Path Sum

Idea

Since the maximum path sum should be returned, we have to loop over every node at least once. A variable for recording the maximum should created.

A maximum path consists of many maximal paths in local areas. That is, if a node parent is on a maximum path, then:

  • Its left subtree must return a maximum path, or
  • Its right subtree must return a maximum path, or
  • Neither left subtree nor right subtree return a maximum path except itself (the case happens when the sum of path is smaller than 0)

As a result, the problem could be splitted into smaller problems. At each recursion, the path sums of left subtree and right subtree are compared. The recursion stops when a node is null. The maximum path is updated if current path sum is larger. Finally, the maximal sum of current tree is returned.

Test cases

Input Expected Output
nums=[1,2,3] 6
nums=[-10,9,20,null,null,15,7] 42

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        int res = traverse(root);

        return max;
    }
    
    private int traverse(TreeNode root) {
        if (root == null)
            return 0;
        
        int leftres = Math.max(0, traverse(root.left));
        int rightres = Math.max(0, traverse(root.right));
        int res = leftres + root.val + rightres;
        max = Math.max(max, res);
        
        return root.val + Math.max(leftres, rightres);
    }
}