二叉树的最大路径和

1. 题目描述

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

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

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

2. 思路

• DFS

3. 实现

3.1. DFS

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt64
    dfs(root, &maxSum)
    return maxSum
}

func dfs(root *TreeNode, maxSum *int) int {
    if root == nil {
        return 0
    }

    //计算左子树能得到的最大和，如果为负数那还不如不要，即为0
    leftMaxSum := max(0, dfs(root.Left, maxSum))
    //计算右子树能得到的最大和，如果为负数那还不如不要，即为0
    rightMaxSum := max(0, dfs(root.Right, maxSum))
    *maxSum = max(*maxSum, root.Val + leftMaxSum + rightMaxSum)
    //返回单边最大路径和，之所以不是返回*maxSum的原因在于*maxSum可能由左右子树组成，再配合root返回那就不是一个路径了
    return root.Val + max(leftMaxSum, rightMaxSum)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. 参考

• 【二叉树中的最大路径和】递归，条理清晰 - 二叉树中的最大路径和 - 力扣（LeetCode）