Ricky.L的随笔
0%

LeetCode.124.二叉树中的最大路径和（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.124.二叉树中的最大路径和（困难）

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

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

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

题解

思路

假设找到了最大路径和的路径，观察这个路径的特点，可以发现路径必然会经过一个根节点，也就是从一个根节点向左和向右延伸可以到达整个路径。

路径和怎么计算？

可以遍历每一个节点，计算当前节点左、右子树上的最大路径和，再与当前节点的值相加即可。

计算路径和的注意事项

这里要注意节点值可能是负数，所以左右子树的路径和可能是负的，越加越小，如果是负的肯定就不加了。

左右子树最大路径和怎么求？

对于某个节点x来说，若其左子树路径和为leftSum，右子树路径和为rightSum，对于x的父节点来说，只能选用leftSum和rightSum种较大的那个，再加上x的值，作为x的父节点的子树路径和。否则就路径就有分叉了，不满足题意。

怎么求最大路径和？

计算每个节点路径和时，记录最大的那个路径和的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun maxPathSum(root: TreeNode?): Int {
        var maxSum = Int.MIN_VALUE
        fun maxGain(root: TreeNode?): Int {
            if (root == null) return 0
            val leftSum = maxOf(0, maxGain(root.left))
            val rightSum = maxOf(0, maxGain(root.right))
            val currentPathSum = root.`val` + leftSum + rightSum
            maxSum = maxOf(maxSum, currentPathSum)
            return root.`val` + maxOf(leftSum, rightSum)
        }
        maxGain(root)
        return maxSum
    }
}