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

题目描述

这是 LeetCode 上的 124. 二叉树中的最大路径和 ，难度为 困难。

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]

输出：6

解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]

输出：42

解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 $[1, 3 \times 10^4]$
• $-1000 <= Node.val <= 1000$

---

递归

一个简单的做法是直接递归来做：设计 DFS 函数，传入当前节点 cur，返回以该节点“往下”延伸所能取得的最大路径和。

即在 仅使用当前节点、使用当前节点和左子树路径 和 使用当前节点和右子树路径 三者中取最大值进行返回。

同时在 DFS 过程中，我们计算「以当前节点 cur 为路径最高点」时的最大路径和，并用此来更新全局变量 ans。

具体的，在以节点 cur 为路径最高点时的最大路径和，首先包含当前节点本身（cur.val），以及可选的左右节点路径和（dfs(cur.left) 和 dfs(cur.right)）。当左右节点路径和不为负数时，说明能够对当前路径起到正向贡献作用，将其添加到路径中。

Java 代码：

class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left), right = dfs(root.right);
        int t = root.val;
        if (left >= 0) t += left;
        if (right >= 0) t += right;
        ans = Math.max(ans, t);
        return Math.max(root.val, Math.max(left, right) + root.val);
    }
}

C++ 代码：

class Solution {
public:
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = dfs(root->left), right = dfs(root->right);
        int t = root->val;
        if (left >= 0) t += left;
        if (right >= 0) t += right;
        ans = max(ans, t);
        return max(root->val, max(left, right) + root->val);
    }
};

Python 代码：

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = float('-inf')
        def dfs(root):
            nonlocal ans
            if not root: return 0
            l, r = dfs(root.left), dfs(root.right)
            t = root.val
            if l >= 0: t += l
            if r >= 0: t += r
            ans = max(ans, t)
            return max(root.val, max(l, r) + root.val)
        dfs(root)
        return ans

TypeScript 代码：

function maxPathSum(root: TreeNode | null): number {
    let ans = -0x3f3f3f3f;
    const dfs = function(root: TreeNode | null): number {
        if (root == null) return 0;
        const l = dfs(root.left), r = dfs(root.right);
        let t = root.val;
        if (l >= 0) t += l;
        if (r >= 0) t += r;
        ans = Math.max(ans, t);
        return Math.max(root.val, Math.max(l, r) + root.val);
    };
    dfs(root);
    return ans;
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

树形 DP

另一个做法是使用「树形 DP」思路来做。

将某个节点所在最佳路径根据方向进行拆分：往左子节点进行延伸、往右子节点进行延伸 和 往父节点进行延伸。

若能分别求解出三个方向的最大路径和，从中选择路径和最大（路径和非零）的两个方向进行累加，便是当前节点的最大路径和。

具体的，创建哈希表记录某个节点三个方向的路径和情况：节点对象作为哈希表的键，三个方向路径和情况作为值。

即键值对格式：节点对象: [父节点方向最大路径和, 左子节点方向最大路径和, 右子节点方向最大路径和]。

然后是常规的树形 DP 求解思路：第一次 DFS 先求解两个“方向往下”的最大路径和。第二次 DFS 根据 首次 DFS 已算好的“方向往下”的路径和情况 以及 本轮 DFS 已递归处理好的当前节点“方向往上”的路径和情况，来求解 当前节点子节点 的“方向往上”路径和情况。

对「树形 DP」接触不深的同学，可以看 前置 🧀

Java 代码：

class Solution {
    Map<TreeNode, int[]> map = new HashMap<>(); // 节点: [父, 左, 右]
    public int maxPathSum(TreeNode root) {
        dfs1(root, null);
        dfs2(root, null);
        int ans = Integer.MIN_VALUE;
        for (TreeNode cur : map.keySet()) {
            int t = cur.val;
            int[] info = map.get(cur);
            Arrays.sort(info);
            if (info[2] >= 0) t += info[2];
            if (info[1] >= 0) t += info[1];
            ans = Math.max(ans, t);
        }
        return ans;
    }
    int dfs1(TreeNode cur, TreeNode fa) {
        if (cur == null) return 0;
        int left = dfs1(cur.left, cur), right = dfs1(cur.right, cur);
        int[] info = map.getOrDefault(cur, new int[3]);
        info[1] = left; info[2] = right;
        map.put(cur, info);
        return Math.max(cur.val, cur.val + Math.max(left, right));
    }
    void dfs2(TreeNode cur, TreeNode fa) {
        if (cur == null) return ;
        int[] curInfo = map.get(cur);
        if (cur.left != null) {
            int[] leftInfo = map.get(cur.left);
            leftInfo[0] = Math.max(cur.val, cur.val + Math.max(curInfo[0], curInfo[2]));
        }
        if (cur.right != null) {
            int[] rightInfo = map.get(cur.right);
            rightInfo[0] = Math.max(cur.val, cur.val + Math.max(curInfo[0], curInfo[1]));
        }
        dfs2(cur.left, cur);
        dfs2(cur.right, cur);
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.124 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。