跳到主要内容

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

本节目标

向父节点只返回单边最大贡献，在当前节点组合左右贡献更新完整路径答案。

这是树上综合问题中区分“向上返回值”和“完整答案”的典型树形 DP。

查看 LeetCode 原题

题意与边界​

路径由不同节点间的父子边连接，至少包含一个节点，不要求经过根，也不要求从根到叶。节点值可以为负，因此全负树的答案是值最大的单个节点，而不是空路径的 0。

单边贡献与完整路径​

dfs(node) 向父节点返回“从 node 出发且只能选择一侧向下延伸”的最大贡献。父节点无法同时接住当前节点的左右两条边，否则路径会分叉。负贡献不如不选，故左右返回值都先与 0 取最大值。

但经过当前节点的完整候选路径可以同时使用左右贡献，值为 node.val + left + right，用全局答案更新。向上返回时只保留 node.val + max(left, right)。入口必须重置答案，避免复用同一对象时保留上一棵树的结果。

正确性依据​

任意简单路径有唯一最高节点。该节点以下的路径至多各从左、右子树选一条连续分支，递归计算出的非负贡献正是每侧最优选择，故当前候选覆盖所有以该节点为最高点的路径。遍历所有节点并取最大值不会漏解；只返回一条分支又保证父节点得到的是连续可延伸路径。

代码实现​

C++17
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        answer = std::numeric_limits<int>::min();
        dfs(root);
        return answer;
    }

private:
    int answer;

    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        int left = std::max(0, dfs(node->left));
        int right = std::max(0, dfs(node->right));
        answer = std::max(answer, node->val + left + right);
        return node->val + std::max(left, right);
    }
};

复杂度分析​

每个节点访问一次，时间复杂度为 O(n)；递归栈深度为 O(h)，其中 h 为树高。

边界与易错点​

  • 把左右贡献之和返回给父节点，会形成分叉而非一条路径。
  • 不丢弃负贡献，会让可选路径变差。
  • 用 0 初始化答案会错误处理全负树。
  • 忘记在入口重置答案，会污染下一次调用。

模式迁移​

直径也在当前节点组合左右信息，但它向上返回高度；遇到“当前节点组合完整结果、父节点只取单边”的题目，应把这两个量分别命名和证明。