LeetCode Binary Tree Maximum Path Sum: DP with Local/Global Maximum

Overview

LeetCode Binary Tree Maximum Path Sum: DFS scan tree to get two local/global maximum path for each node, values for root node can be calculated with DP.

LeetCode Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1
      / \
     2   3

Return 6.

Analysis: DP with Local/Global Maximum

DP:  Let F(root) denote the maximum path sum of the tree rooted at root. Then we have the following recursive formula.

F(root) = max {   F(root->left),  F(root->right), root->val., root->val + left path, root->val + right path, root->val + left path + right path }

That is, the maximum path sum, is either in the left subtree (root->left), or the right subtree (root->left), or the path cross the root (i.e., the root is included in the path). And for the path cross the root, we again have four cases: (1) the path only contain the root (root->val) (2) the path only contain the root and the path in the left subtree (3) the path only contain the root and the path in the right subtree (4) the path contain the root and also contain paths in left and right subtree.

Once we get this dp formula, it is easy to implement it. And also note that to update the left path and right path, the correct formula would be left path = max(max(root->left’s left path, root->left’s right path) + root->val, root->val) because both the left path and the right path could be negative sum values which does not help maximize the correct path.

Based on the above recursive definition, the the left path and the right path could actually be simplified into a single path starting from the root, so for each node we maintain two values:

  1. Local Maximum: Maximum path starting from root, let’s call it L, then L(root) = max(root->val, max(L(root->left), L(root->right)) + root->val)
  2. Global Maximum: The Maximum Path over the whole tree, Let’s call it G, then G(root) = max(root->val + L(root->left) + L(root->right), L(root), G(root->left), G(root->right)).

The following simple code implements the simplified version and could pass the LeetCode OJ for this Binary Tree Maximum Path Sum problem:

class Solution {
    public:

        void dfs(TreeNode *root, pair<int, int> *pRet) {
            if (NULL == root->left && NULL == root->right) {
                pRet->first = pRet->second = root->val;
                return ;
            }

            pair<int, int> lPath(INT_MIN, INT_MIN), rPath(INT_MIN, INT_MIN);
            if (root->left)  
                dfs(root->left, &lPath);
            if (root->right) 
                dfs(root->right, &rPath);

            pRet->second = max(root->val, max(lPath.second, rPath.second) + root->val);
            
            int c = root->val;
            if (root->left) 
                c += lPath.second;
            if (root->right)
                c += rPath.second;

            pRet->first = max( max(lPath.first, rPath.first), max(pRet->second, c));

        }

        int maxPathSum(TreeNode *root) {
            if (NULL == root) 
                return 0;

            pair<int, int> ret;
            dfs(root, &ret);
            return ret.first; 
        }
};

Binary Tree Maximum Path Sum Remarks:

It is kind of fuzzy on the negative numbers. The problem actually asks the path should at least contain one node, so when all the nodes are negative values, we need to return the one with the largest negative number. If the problem allow empty (NULL) path, then the minimum sum would be 0, which actually leads to easier solution.

Summary

LeetCode Binary Tree Maximum Path Sum: DFS scan tree to get two local/global maximum path for each node, values for root node can be calculated with DP

Written on June 16, 2013