题目描述

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

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

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

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：
● 树中节点数目范围是 [1, 3 * 104]
● -1000 <= Node.val <= 1000
附上力扣链接https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
这里需要注意，实例给的输入虽然看起来像数组，但并不是数组结构，力扣给的输入直接就是二叉树结构，每个节点分别包含val、left、right三部分

递归实现

代码

我们先看代码，代码并不长

let maxPathSum = function(root){
    let ret
    getMax(root)
    function getMax(r){
        if(r === null) return 0
        let left = Math.max(0, getMax(r.left))
        let right = Math.max(0, getMax(r.right))
        ret = ret ? Math.max(ret, left + right + r.value) : left + right + r.value
        return Math.max(left, right) + r.value
    }
    return ret
}

let root = createTree(1, 2, 3, 4, 5, null, 6, null, 7)

console.log(maxPathSum(root))

这里的createTree方法是在上一篇文章中说到的构建二叉树的方法，这里附上链接https://blog.csdn.net/wuxian_wj/article/details/122096201

思路解析

咱们来一步一步分析一下具体思路，这道题主要是想要最大路径和，也就是整棵树中，一个点到另一个点路径上所有节点的值相加大于所有节点到节点的和。那么自然是要自底向上的计算。用ret变量记录当前最大路径和，判断根节点左右子树与与其自身值相加是否大于ret。具体细节我们一步一步来整理。
● 主要看getMax()中的逻辑，如果当前轮根节点为空自然是直接返回0
● 如果不为空的计算其左子树上的最大路径和，这里是用递归法，将其左子树一步步拆分，某个节点没有左子树则向上返回。
● 右子树同理
● 为什么要用Math.max(0, getMax(r.left))是因为，当某个节点的左子树或者右子树上最大路径和为负数则将其舍弃至零，下一轮向上溯源是的最大路径和一定不包含最大路径和为负数的子树。
● 接下来我们需要注意，在某一轮中当前轮根节点与其左右子树的最大路径和相加的值就是当前轮的最大路径和，我们需要判断其值与ret中保存的值谁更大，如果当前轮最大路径和大于ret那么将其赋值给ret，如果不大于ret值不变，保证ret中保存的是所有情况下最大的路径和。
● 最后通过一个return以后就要向上一层溯源了，我们需要返回当前轮的最大路径和，作为上层的子树。但是路径是指一个点到另一个点，所以我们需要从左子树和右子树的最大路径和中取最大加上当前根节点的值就是本轮的最大路径和。
● 当走到整棵二叉树的根节点时，就到了递归的出口，每一条路径都走过，ret中则保存着所有路径下最大的路径和，返回ret即可