Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Description:

Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.

Example:

Given the below binary tree:

 1
/
2  3

return 6.

分析：

   分而治之。

思路：

Code：

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
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxPathSum(TreeNode *root) {
        // write your code here
        return helper(root).combinedPathMax;
    }
private:
	class PathSumType {
	public:
		int singlePathMax;
		int combinedPathMax;
		PathSumType(int singlePathMax, int combinedPathMax) {
			this->singlePathMax = singlePathMax;
			this->combinedPathMax = combinedPathMax;
		}
	};
	
	PathSumType helper(TreeNode *root) {
		if (root == nullptr) return PathSumType(0, INT_MIN);
		PathSumType left = helper(root->left);
		PathSumType right = helper(root->right);

		int singlePathMax = max(left.singlePathMax, right.singlePathMax) + root->val;
		singlePathMax = max(0, singlePathMax);

		int combinedPathMax = max(left.combinedPathMax, right.combinedPathMax);
		combinedPathMax = max(combinedPathMax, left.singlePathMax + right.singlePathMax + root->val);

		return PathSumType(singlePathMax, combinedPathMax);
	}
};