LeetCode: 124. Binary Tree Maximum Path Sum

题目描述

Given a 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.

For example:
Given the below binary tree,

       1
      / \      2   3

Return 6.

题目大意： 找到给定二叉树的最大路径和(从任意节点到任意节点)

解题思路

相关定义

• 记 HalfPath(root) 为 “二叉树 root 上一条包含根节点 root 的路径，该路径上只有父子节点，没有兄弟节点 “。
  如下图， ABD 和 ABE 就是 HalfPath(A) 的两种可能的情况。
  
  
• 记 maxHalfPath(root) 为 “HalfPath(root) 路径和的最大值”。
• 记 maxPathSum(root) 为题目所求的，二叉树 root 的 最大路径和。

maxPathSum(root) 的求解

• maxPathSum(root) 的路径可能出现在其左子树或右子树，即 maxPathSum(root) 可能等于 maxPathSum(root->left), maxPathSum(root->right) 。如下图, maxPathSum(A) = maxPathSum(A的左子树):
  
• maxPathSum(root) 的路径也可能由 maxHalfPath(root->left) 的路径, maxHalfPath(root->right) 的路径和 root 构成的。即 maxPathSum(root) 可能等于 maxHalfPath(root->left) + maxHalfPath(root->right) + root->val。 如下图,maxPathSum(A) = maxHalfPath(A的左子树) + maxHalfPath(A的右子树) + A节点的值:
  
• 当然， maxPathSum(root) 的路径也可能只由 maxHalfPath(root->left) 的路径或 maxHalfPath(root->right) 的路径加上 root 构成的(即 maxHalfPath(root)的路径)。如下图: maxPathSum(A) = maxHalfPath(A的左子树) + A节点的值 = maxHalfPath(A)。
  
• maxHalfPath(root) 的最终值取上述所有可能情况的最大值。

maxHalfPath(root) 的求解

• maxHalfPath(root) 的路径可能由 maxHalfPath(root->left) 的路径或 maxHalfPath(root->right) 的路径加上 root 节点所构成的。如下图, maxHalfPath(A) 的路径是由 maxHalfPath(A的左子树) 的路径加上 A 节点构成的:
  
• maxHalfPath(root) 的路径也有可能只由 root 节点构成(当 maxHalfPath(root->left) 和 maxHalfPath(root->left) 为负时)。 如下图， maxHalfPath(A) 的路径是由 A 节点构成。
  
• maxHalfPath(root) 的最终值取上述所有可能情况的最大值。

AC 代码

/** * 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 {
private:
    // 返回 root 的 maxPathSum（first）和 包含 root 的最大 HalfPath 路径和(second)
    pair<long int, long int> maxPathSumRef(TreeNode* root)
    {
        if(root == nullptr) return  {INT_MIN, INT_MIN};

        pair<long int, long int> leftPathSum = maxPathSumRef(root->left);
        pair<long int, long int> rightPathSum = maxPathSumRef(root->right);

        long int pathSum = INT_MIN;
        long int halfPathSum = INT_MIN;

        // 求树 root 的 max halfPathSum
        halfPathSum = max(root->val + rightPathSum.second, root->val + leftPathSum.second);
        halfPathSum = max(halfPathSum, (long int)root->val);

        // 求树 root 的 max pathSum
        pathSum = max(leftPathSum.first, rightPathSum.first);
        pathSum = max(pathSum, root->val + leftPathSum.second+rightPathSum.second);
        pathSum = max(pathSum, halfPathSum);

        return {pathSum, halfPathSum};
    }
public:
    int maxPathSum(TreeNode* root) {
        return maxPathSumRef(root).first;
    }
};