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

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

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

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

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

2、题目描述

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

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

给你一个二叉树的根节点 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、思路分析

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

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

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

2、代码实现

代码参考：

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);
    }
}

3、时间复杂度

时间复杂度 ： O(N)

其中N是二叉树中的节点个数。

空间复杂度： O(N)

其实N是二叉树中的节点个数。

三、总结

对根节点调用函数maxGain就可得到每个节点的节点值之和。

维护一个全局变量maxSun存储最大路径和，在递归过程中更新maxSum的值。

最后得到的maxSum的值即为二叉树的最大路径和。