Problem description:

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
Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

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

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Solution:

The idea of this question is to do dfs with a global variable. We design a dfs function that help to

  1. computes the maximum path sum with highest node is the input node, update maximum if necessary.
  2. returns the maximum sum of the path that can be extended to input node’s parent.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        
        self.res = float("-inf")
        def dfs(root):
            if not root:
                return 0
            right = max(dfs(root.right), 0)
            left = max(dfs(root.left), 0)
            self.res = max(self.res, root.val + right + left)
            return root.val + max(right, left)
        dfs(root)
        return self.res
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int result= INT_MIN;
        dfs(root, result);
        return result;
    }
    
    int dfs(TreeNode* root, int& result){
        if(!root) return 0;
        int left= max(0, dfs(root->left, result));
        int right= max(0, dfs(root->right, result));
        
        result= max(result, left+right+root->val); //use root as the lowest common ancestor, which is the highest node to compare with current maximum result
        return max(left, right)+root->val;
    }
};

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/NGnBtX