Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

0%

# Leetcode 124 二叉树中的最大路径和(Binary Tree Maximum Path Sum) 题解分析

发表于 2021-01-24 分类于 Java ， leetcode ， Binary Tree ， java ， Binary Tree 阅读次数： 阅读次数： Disqus：

### 题目介绍

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the `root` of a binary tree, return the maximum path sum of any path.

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

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

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

### 简要分析

其实这个题目会被误解成比较简单，左子树最大的，或者右子树最大的，或者两边加一下，仔细想想都不对，其实有可能是产生于左子树中，或者右子树中，这两个都是指跟左子树根还有右子树根没关系的，这么说感觉不太容易理解，画个图
可以看到图里，其实最长路径和是左边这个子树组成的，跟根节点还有右子树完全没关系，然后再想一种情况，如果是整棵树就是图中的左子树，那么这个最长路径和就是左子树加右子树加根节点了，所以不是我一开始想得那么简单，在代码实现中也需要一些技巧

### 代码

    int ansNew = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
            maxSumNew(root);
            return ansNew;
        }

    public int maxSumNew(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 这里是个简单的递归，就是去递归左右子树，但是这里其实有个概念，当这样处理时，其实相当于把子树的内部的最大路径和已经算出来了
        int left = maxSumNew(root.left);
        int right = maxSumNew(root.right);
        // 这里前面我有点没想明白，但是看到 ansNew 的比较，其实相当于，返回的是三种情况里的最大值，一个是左子树+根，一个是右子树+根，一个是单独根节点，
        // 这样这个递归的返回才会有意义，不然像原来的方法，它可能是跳着的，但是这种情况其实是借助于 ansNew 这个全局的最大值，因为原来我觉得要比较的是
        // left, right, left + root , right + root, root, left + right + root 这些的最大值，这里是分成了两个阶段，left 跟 right 的最大值已经在上面的
        // 调用过程中赋值给 ansNew 了
        int currentSum = Math.max(Math.max(root.val + left , root.val + right), root.val);
        // 这边返回的是 currentSum，然后再用它跟 left + right + root 进行对比，然后再去更新 ans
        // PS: 有个小点也是这边的破局点，就是这个 ansNew
        int res = Math.max(left + right + root.val, currentSum);
        ans = Math.max(res, ans);
        return currentSum;
    }

这里非常重要的就是 ansNew 是最后的一个结果，而对于 maxSumNew 这个函数的返回值其实是需要包含了一个连续结果，因为要返回继续去算路径和，所以返回的是 currentSum，最终结果是 ansNew

### 结果图

难得有个 100%，贴个图哈哈