☆打卡算法☆LeetCode 124. 二叉树中的最大路径和算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“沿父节点到任意子节点，求路径中各节点的总和，返回最大路径和。”

题目链接：

来源：力扣（LeetCode）

链接： 124. 二叉树中的最大路径和 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

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

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

代码语言：javascript复制

示例 1：
输入： root = [1,2,3]
输出： 6
解释： 最优路径是 2 -> 1 -> 3 ，路径和为 2   1   3 = 6

代码语言：javascript复制

示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15   20   7 = 42

二、解题

1、思路分析

这道题就是计算从根节点出发到所有子节点的路径的节点值之和最大的数。

可以使用递归算法，得到子节点到根节点的节点值。

如果节点值为正则记入最大路径和，否则不计入该节点的最大路径和。

2、代码实现

代码参考：

代码语言：javascript复制

class Solution {
    int maxSum = Integer.MIN_VALUE;

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

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

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

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

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