124. 二叉树中的最大路径和

Introduction

Question：124. 二叉树中的最大路径和

Analysis

之前一直觉得挺难的，但感觉好像做过。

我们把maxPathSum转化成一个新的简单问题，即求解以root为起点的最大路径和，为了方便描述，我们将其称为maxRootPathSum。

这个问题比较好解决，可以转化成递推式：maxRootPathSum(root)=root->val + max(maxRootPathSum(root->left),maxRootPathSum(root->left))

同时，我们可以归纳得到maxPathSum只有三种可能：

• maxPathSum(root) = maxRootPathSum(root)
• maxPathSum(root) = root->val + maxRootPathSum(root->left) + maxRootPathSum(root->right)

因此很容易写出一个递归的解法。

Implement

int maxSum;
int maxPathSum(TreeNode* root) {
    maxSum = INT_MIN;
    maxRootPathSum(root);
    return maxSum;
}
int maxRootPathSum(TreeNode *root) {
    if (root == nullptr) return 0;
    // cout << root->val << endl;
    int left = maxRootPathSum(root->left);
    int right = maxRootPathSum(root->right);
    // cout << left << " " << right << endl;
    int res = max(root->val, max(root->val + left, root->val + right));
    maxSum = max(maxSum, max(res, root->val + left + right));
    return res;
}