[LeetCode] 124. Binary Tree Maximum Path Sum

Posted on | In

Problem

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.

Example 1:

1
2
3
4
5
6
7
Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Explanation

  1. This problem is different from the general path sum problem, in this problem, path sum can starts in non-root, and it can also end in non-leaf.

  2. This kind of path can be concluded in two types:

    1. root->leaf path, in example1’s 1->2 or 1->3.
    2. Two nodes are connected by their lowest common ancestor (LCA) node, in example1’s 2->1->3.

  3. Apprently, top-down’s recursion method doesn’t work because in type2’s path, its path sum is depends on LCA’s left and right sub path’s maximum, and this type of path sum cannot be obtained from top-down recursion method.

  4. Therefore, we can use bottom-up’s recursion method. Let say node x,

    1. Define PS1(x) is from node x to leaf’s first type’s path sum.
    2. Define PS2(x) is node x as LCA’s second type path’s path sum.
    3. So, if we find all node x’s PS1 and PS2, then we can find the max path sum.

  5. How to find PS1(x) and PS2(x)?

    1. PS1(x) and PS2(x) are not less than x-val because x itself can be a single node path.
    2. PS1(x) and PS2(x) can be found in PS1(x-left) and PS1(x-right):
      1. PS1(x) = max [ max(PS1(x->left), 0), max(PS1(x->right), 0) ] + x->val
      2. PS2(x) = max(PS1(x->left), 0) + max(PS1(x->right), 0) + x->val

  6. We need to return PS1(x) for its upper layer’s node to calculate PS1 and PS2.

  7. For leaf node, PS1(x) = PS2(x) = x->val.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
     class Solution {
 public:
     int maxPathSum(TreeNode *root) {
         int maxSum = INT_MIN;
         int ps1_root = findMaxPathSum(root, maxSum);
         return maxSum;
     }

     int findMaxPathSum(TreeNode *root, int &maxSum) {
         if(!root) return 0;

         int ps1_left = 0, ps1_right = 0;
         if(root->left)
             ps1_left = max(findMaxPathSum(root->left,maxSum),0);
         if(root->right)
             ps1_right = max(findMaxPathSum(root->right,maxSum),0);

         int ps1_root = max(ps1_left, ps1_right) + root->val;
         int ps2_root = ps1_left + ps1_right + root->val;
         maxSum = max(maxSum,max(ps1_root, ps2_root));

         return ps1_root;
     }
 };

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = Integer.MIN_VALUE;

    int helper(TreeNode root) {
        if (root == null) return 0;
        int singleLeft = 0;
        int singleRight = 0;

        if (root.left != null) {
            singleLeft = Math.max(0, helper(root.left));
        }
        if (root.right != null) {
            singleRight = Math.max(0, helper(root.right));
        }

        int singlePath = Math.max(singleLeft, singleRight) + root.val;
        int bothPath = singleLeft + singleRight + root.val;
        max = Math.max(max, Math.max(singlePath, bothPath));

        return singlePath;
    }
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
}