0bf4ec81c97e4d4eb476f537c2593593.png

【题目】：124. 二叉树中的最大路径和

这题有两个关键点：

  1. 更新res：res = max(l + r + root->val, res)，左子树最大链长 + 右子树最大链长 + 根节点的值其实也可以当成一条链
  2. 子树root的最大链长：max(max(l, r) + root->val, 0)，由于一个子树的链长只能取左子树的最大链长或右子树的最大链长，所以这里先max(l, r)，也别忘了+root->val，由于这个值可能比0还小，如果比0小那要你还有什么用？直接舍弃好了（0表示什么都不取）
    ac69788e56a54247af5d4c3c2abd327f.png
class Solution {
public:
    int res = INT_MIN;
    int help(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        int l = help(root->left); // 左子树的最大链和
        int r = help(root->right); // 右子树的最大链和
        res = max(l + r + root->val, res); // l + r + root->val：左右子树的联合可以拼成一条链
        return max(max(l, r) + root->val, 0); // 当前子树的联和：max(l, r) + root->val，因为是链，所以左右子树只能取一条
    }
    int maxPathSum(TreeNode* root) {
        help(root);
        return res;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)