二叉树中的最大路径和 - LeetCode 热题 50

大家好！我是曾续缘😸

今天是《LeetCode 热题 100》系列

发车第 50 天

二叉树第 15 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

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

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

给你一个二叉树的根节点 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 * 10⁴]
-1000 <= Node.val <= 1000
难度：💝💝💝

解题方法

我们可以采用递归的方式，从根节点开始遍历整个二叉树，在遍历过程中，对于每个节点，我们需要计算包含该节点的路径的最大值，并更新全局最大路径和。因为路径是一条节点序列，所以必定包括某个节点作为路径的根节点，我们可以尝试着将每个节点作为路径的根节点，以此来寻找整个二叉树的最大路径和。

假设现在已经以某个节点为根节点了，那么它的组成应该是什么样的呢？首先，根节点的值是必然要计算进去的，但是对于根节点的左子树部分和右子树部分，它们的贡献是不确定的，因此我们需要分别计算左右子树部分的最大路径和，然后取其中的较大值作为这个节点的贡献。具体地，我们可以定义一个递归函数 sum_from_root，该函数返回以当前节点为根节点的子树中，包括当前节点的单侧路径最大和，并更新全局最大路径和。对于一个节点的计算，它包含以下几个步骤：

若当前节点为空，则返回 0。
对左右子树分别递归调用 sum_from_root 方法，并取结果与 0 的较大值。
计算当前节点值加上左右子树单侧路径和的和，并与全局最大路径和比较，更新最大路径和。
返回当前节点值加上左右子树单侧路径和的较大值。

在递归过程中，如果子树的贡献为负数，那么我们就可以认为不选该子树会更好一些，此时我们将该子树的贡献设为 0。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans = Integer.MIN_VALUE;
    private int sum_from_root(TreeNode root){
        if(root == null){
            return 0;
        }
        int l = Math.max(sum_from_root(root.left), 0);
        int r = Math.max(sum_from_root(root.right), 0);
        ans = Math.max(ans, root.val + l + r);
        return root.val + Math.max(l, r);
    }
    public int maxPathSum(TreeNode root) {
        sum_from_root(root);
        return ans;
    }
}