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

124. 二叉树中的最大路径和 - 力扣（LeetCode）

class Solution {
  int64_t GlobalMax{INT_MIN};

  int Visit(TreeNode *Root) {
    if (!Root)
      return INT_MIN;

    int64_t LMax = Visit(Root->left);
    int64_t RMax = Visit(Root->right);

    int64_t LRoot = LMax + Root->val;
    int64_t RootR = Root->val + RMax;
    int64_t LRootR = LMax + Root->val + RMax;

    // Local max can be calculated from M/LM/MR/LMR
    int64_t LocalMax = std::max((int64_t)Root->val, std::max(LRootR, std::max(LRoot, RootR)));
    // Global max can be updated using local max
    GlobalMax = std::max(LocalMax, GlobalMax);
    // Propagated value can be calculated from M/LM/MR
    return std::max((int64_t)Root->val, std::max(LRoot, RootR));
  }
public:
  int maxPathSum(TreeNode* root) {
    Visit(root);
    return GlobalMax;
  }
};

这道 Hard 确实不错，增长信心。核心在于知道 LocalMax 和返回值计算的差别：LocalMax 可以经过左、根、右，但返回值传递（propagate）的时候就只能传递左、根或者根、右了。

其实我的方法还是有点保守了，官方的方法是直接忽略小于 0 的节点值——实际上这是正确的，因为我们要求的也就是最大和。官解还不用 int64_t 这种 hack。

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        maxSum = max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

此外注意一下：在遍历开头写 if (!Root) return 0; 是比每次向左、右遍历的时候提前判别 if (Root->left) Visit(Root->left); 要更简洁的。而且不动点和不动点对应的值即 return 0; 还更明确。

二刷

class Solution {
  int Sum{INT_MIN};
  int Traverse(TreeNode *TN) {
    if (!TN)
      return 0;

    int Val = TN->val;
    int Left = Traverse(TN->left);
    int Right = Traverse(TN->right);
    // N LN NR
    int Propagation = std::max(Val, std::max(Left + Val, Val + Right));
    // S N LN NR LNR
    Sum = std::max(Sum, std::max(Propagation, Left + Val + Right));
    return Propagation;
  }
public:
  int maxPathSum(TreeNode* root) {
    Traverse(root);
    return Sum;
  }
};

其实我这个好像也用不着什么 hack 吧……不知道一刷怎么写的。官解的 maxGain() 的优势在于它的这个思维方式似乎很适合做 DP，就，状态转移方程，懂我意思吧。

而且官解最后那句 return node->val + maxGain; 固定把 node->val 加上去确实也是一种不错的思考方式——无论怎么样，我们的 propagation 过程都是需要经过根节点的。