原題

LintCode 94. 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.

解題

題意是找到整棵樹中，值最大的一條路徑。

對于一個節(jié)點而言，值最大的路徑其實就等于，左邊的節(jié)點的值最大路徑+右邊節(jié)點的值最大路徑+自己的值（當(dāng)然前提條件是這些值都大于0，小于0的應(yīng)該被舍棄）。

那么我們可以維護一個結(jié)果值，并從根節(jié)點開始尋找值最大路徑，只要找到比結(jié)果值大的就更新結(jié)果值。

代碼

/**
 * 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
        if (root == NULL) return 0;
        helper(root);
        return res;
    }
private:
    int res = INT_MIN;
    int helper(TreeNode *root) {
        if (root == NULL) return 0;
        int left = helper(root->left);
        int right = helper(root->right);
        int cur = root->val + max(left, 0) + max(right, 0);
        res = max(res, cur);
        return root->val + max(left, max(right, 0));
    }
};