LeetCode 实战：「图解」二叉树中的最大路径和

秒速五厘米 2024-04-17 17:38 13阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | P.yh

来源 | 五分钟学算法

### 题目描述 ###

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径 **至少包含一个节点** ，且不一定经过根节点。

**示例 1:**

输入: [1,2,3]
    
       1
      / \
     2   3
    
    输出: 6

**示例 2:**

输入: [-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
    输出: 42

### 题目分析 ###

这是一道二叉树问题中比较难的题目。

题目要求出一个二叉树的最大路径和，路径和就是把一条路径上面节点的值加起来，这一题的难点在于路径的方向不固定，只要是任意两点间的通路都算是**有效路径**。

一般来说，解决树的问题都需要用到递归，**树上的搜索，本质上也是深度优先搜索**。

这里会有两种考虑方式，一个是**自底向上的分治**，也就是进入递归，一开始不做任何节点上面的计算或者是处理，直接进入到下一层递归，直到到了最底层，然后再开始计算并返回答案，然后上层树节点的递归函数就会收到下层返回的结果，这样做的好处是，一个节点可以获知其子树的局部答案；

另外一个是**自顶向下的遍历搜索**，这个和之前的思路完全相反，也就是先处理当前节点的内容，处理完后去到下一层节点，这种方法一般没有返回值，但是一般会有一个全局或者是引用变量，用来记录遍历过程中的内容。

我们再回过头来看这道题，在递归遍历的过程中，对于当前节点，其在路径中可以是路径尾，路径头（假设路径是从上到下的，其实在这道题中，没有头尾的概念），也可以是路径中的一个节点。

那怎么判断呢？

这时我们得需要当前节点左右子树的信息，所以我们可以考虑使用之前提到的 **自底向上** 的分治，有了当前节点，左右子树到当前节点的最大路径，我们可以看看这里会有几种情况，我用 **root** 表示当前节点，**left** 表示左子树到 root 的最大和的路径，**right** 表示右子树到 root 的最大和的路径：

*  root 和左右路径形成路径（left - root - right）
 *  root 和左路径形成路径（left - root）
 *  root 和右路径形成路径（root - right）
 *  root 自成路径（root）

你可以看到这四种情况都会把当前节点考虑在内，我们可以更新这里的最大值。

但是需要注意的是，我们返回的时候，第一种情况是不能返回的，因为对于上一层节点来说，其无法形成有效的路径，因此我们只需要将 2，3，4 中的最大值返回即可，当然，更新全局答案的时候，这 4 种情况都需要考虑在内的。

### 动画描述 ###

### 代码实现 ###

private int maximum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
    
        helper(root);
    
        return maximum;
    }
    
    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 如果左右子树返回的最大路径值小于 0
        // 直接将值设为 0，也就是不考虑对应的路径
        int leftMax = Math.max(0, helper(root.left));
        int rightMax = Math.max(0, helper(root.right));
        //自底向上的分治,直到到了最底层，才开始计算并返回答案
        maximum = Math.max(root.val + leftMax + rightMax, maximum);
    
        return Math.max(leftMax + root.val, rightMax + root.val);
    }

--------------------

![640?wx\_fmt=gif][640_wx_fmt_gif]

● [用好这 42 款 Chrome 插件，每年轻松省出一个年假][42 _ Chrome]

● [【算法之美】改变世界的十位算法大师][Link 1]

● [把 14 亿中国人都拉到一个微信群在技术上能实现吗？][14]

● [全球最厉害的 14 位程序员！][14 1]

— **完** —

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d96e014a47e14d078f21a6f8b7ca7c2f.png
[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/96e9260b43cd40c1af74633a0e84f384.gif
[42 _ Chrome]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486210&idx=1&sn=c558fabadee9f13ea1254dbaae485306&chksm=fa0e6483cd79ed95120dfdaf461b93e4168cfaf1503a984a2a8962db654a967d2cd282811df8&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486190&idx=1&sn=8a4f15f98882c4847185a2257f7a344a&chksm=fa0e656fcd79ec79dabcb010f2f72e2ae399f9fba9083567a81dcf0e5a85fd771ccf507c8b4e&scene=21#wechat_redirect
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486185&idx=1&sn=02bedd9f0b7b07138913b457d8cda4c4&chksm=fa0e6568cd79ec7e4b799d098a5b6e37e53fc8e8b9b819e78142e768e64a8da0c06bc7768d75&scene=21#wechat_redirect
[14 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/1178053e10564b5e94b9a29d3c18f5e9.png