2014.2.12 23:49

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.

Solution:

　　The maximum path sum of a tree is a path from two nodes in the tree, that sums up to the maximal value possible. The path can always be divided into three parts: root, left path, right path. There might be nodes with negative weight, so the left and right paths could be empty when it is impossible to find a path with positive weight sum.

　　The maximum path sum of node root consists of root->val, the left path sum and the right path sum. That's exactly how the recursion is defined.

　　The return value of the recursive function is the maximal single path sum you can get from the node root, it's either left path or right path, but the result we desire is the maximum path sum possible, which includes both paths. Thus we'll need another global variable to record the greatest one.

　　Here in my code, sum_single refers to the top-down single path, while sum_double refers to the path sum defined in the problem description.

　　Total time complexity is O(n). Space complexity is O(n) as well.

　　T(n) = 2 * T(n / 2) + O(1), you know how to prove T(n) = O(n), right?

Accepted code:

1 // 1WA, 1AC, recursive solution in O(n) time. 2 #include 
     
       3 #include 
      
        4 using namespace std; 5  6 /** 7  * Definition for binary tree 8  * struct TreeNode { 9  *     int val;10  *     TreeNode *left;11  *     TreeNode *right;12  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}13  * };14  */15 class Solution {16 public:17     int maxPathSum(TreeNode *root) {18         max_val = INT_MIN;19         maxPathSumRecursive(root);20         21         return max_val;22     }23 private:24     int max_val;25     26     // return the maximum root-to-leaf sum, the 'root' refers to the current node as the root.27     int maxPathSumRecursive(TreeNode *root) {28         if (root == nullptr) {29             return 0;30         }31         // the root-to-leaf sum32         int sum_single;33         // the leaf-to-leaf or root-to-leaf sum34         int sum_double;35         int max1 = 0, max2 = 0;36         37         sum_double = sum_single = root->val;38         if (root->left != nullptr) {39             max1 = maxPathSumRecursive(root->left);40             if (max1 < 0) {41                 max1 = 0;42             }43         }44         if (root->right != nullptr) {45             max2 = maxPathSumRecursive(root->right);46             if (max2 < 0) {47                 max2 = 0;48             }49         }50         sum_single += max(max1, max2);51         sum_double += max1 + max2;52         if (sum_double > max_val) {53             max_val = sum_double;54         }55         56         return sum_single;57     }58 };