Binary Tree Maximum Path Sum

题目描述：

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 non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000

思路:

使用dfs遍历，返回左或者右子树加上自身值的最大值，算最大值的时候需要特殊处理，需要计算左+右子树+自身值是否是最大值，是就更换最大值。

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
    if root == nil{
        return 0
    }
    maxNum := -99999
    var dfs func(root *TreeNode)int
    dfs = func(root *TreeNode)int{
        if root == nil{
            return 0
        }
        l := dfs(root.Left)
        r := dfs(root.Right)
        maxNum = max(maxNum, max(root.Val, max(root.Val+l,max(root.Val+r, root.Val+r+l))))
        root.Val = max(root.Val, max(root.Val+l,root.Val+r))
        return root.Val
    }
    dfs(root)
    return maxNum
    
}

func max(i, j int)int{
    if i >j{
        return i
    }else{
        return j
    }
}

代码效率：

执行用时：16 ms, 在所有 Go 提交中击败了80.91%的用户
内存消耗：7.4 MB, 在所有 Go 提交中击败了89.68%的用户