原题

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.

解题

题意是找到整棵树中，值最大的一条路径。

对于一个节点而言，值最大的路径其实就等于，左边的节点的值最大路径+右边节点的值最大路径+自己的值（当然前提条件是这些值都大于0，小于0的应该被舍弃）。

那么我们可以维护一个结果值，并从根节点开始寻找值最大路径，只要找到比结果值大的就更新结果值。

代码

/**
 * 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));
    }
};