124. 二叉树中的最大路径和

发表于 | 分类于
一道比较简单的 hard

用时 ：30min

看懂题目的意思之后其实就能很快的做出来

题意是要求从任意节点出发的值，我们可以把每个节点的值求出来的过程中，选择最大的

又因为路径不能返回，可以知道我们出发的根节点的子节点的路径只能选择左或者右，或者都不要，结果为 x

求max 的时候再 把 x 和 左右都选的情况进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
var maxPathSum = function(root) {
    var max = -Infinity
    var DFS = function (root) {
        if (!root) return 0
        var leftSum = DFS(root.left)
        var rightSum = DFS(root.right)
        var res =  Math.max(leftSum + root.val  ,rightSum + root.val ,root.val)
        max = Math.max(max,res,root.val + leftSum + rightSum)
        return res
    }
    DFS(root)
    return max
};