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

发表于 更新于 分类于 ， ， ， ， 阅读次数： 阅读次数： 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 ，返回其 最大路径和

简要分析

其实这个题目会被误解成比较简单，左子树最大的，或者右子树最大的，或者两边加一下，仔细想想都不对，其实有可能是产生于左子树中，或者右子树中，这两个都是指跟左子树根还有右子树根没关系的，这么说感觉不太容易理解，画个图

可以看到图里，其实最长路径和是左边这个子树组成的，跟根节点还有右子树完全没关系，然后再想一种情况，如果是整棵树就是图中的左子树，那么这个最长路径和就是左子树加右子树加根节点了，所以不是我一开始想得那么简单，在代码实现中也需要一些技巧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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%，贴个图哈哈