124. Binary Tree Maximum Path Sum

题目链接

tag:

• Hard;
• Depth-first Search;

question:
  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:

Input: [1,2,3]
    1
    / \
   2 3
Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]
    -10
    / \
   9 20
    / \
   15 7
Output: 42

思路：
  首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况:

• 最大路径包含该根节点：
  最大路径之和=根节点的值+深度遍历其左子树的路径和的最大值 +深度遍历其右子树的路径和的最大值
• 最大路径不包含该根节点：
  ①该根节点的左孩子作为新的根节点的最大路径和
  ②该根节点的右孩子作为新的根节点的最大路径和
  最大路径和为三者中的最大值。

  在递归函数中，如果当前结点不存在，那么直接返回0。否则就分别对其左右子节点调用递归函数，由于路径和有可能为负数，而我们当然不希望加上负的路径和，所以我们和0相比，取较大的那个，就是要么不加，加就要加正数。然后我们来更新全局最大值结果res，就是以左子结点为终点的最大path之和加上以右子结点为终点的最大path之和，还要加上当前结点值，这样就组成了一个条完整的路径。而我们返回值是取left和right中的较大值加上当前结点值，因为我们返回值的定义是以当前结点为终点的path之和，所以只能取left和right中较大的那个值，而不是两个都要，参见代码如下：

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