二叉树中的最大路径和。路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。力扣124。
递归。x是其中一个节点。
1.无x。
1.1.左树整体的maxsum。
1.2.右树整体的maxsum。
2.有x。
2.1.只有x
2.2.x+左树路径。
2.3.x+右树路径。
2.4.x+左树路径+右树路径。。
时间复杂度：O(N)。
空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
head := NewTreeNode(4)
head.left = NewTreeNode(-7)
head.right = NewTreeNode(-5)
head.left.left = NewTreeNode(9)
head.left.right = NewTreeNode(9)
head.right.left = NewTreeNode(4)
head.right.right = NewTreeNode(3)
maxPath := getMaxSumPath(head)
for _, n := range maxPath {
fmt.Println(n.val)
}
}
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func NewTreeNode(v int) *TreeNode {
res := &TreeNode{}
res.val = v
return res
}
func maxPathSum(root *TreeNode) int {
if root == nil {
return 0
}
return process(root).maxPathSum
}
// 任何一棵树，必须汇报上来的信息
type Info struct {
maxPathSum int
maxPathSumFromHead int
}
func NewInfo(path0, head int) *Info {
ans := &Info{}
ans.maxPathSum = path0
ans.maxPathSumFromHead = head
return ans
}
func process(x *TreeNode) *Info {
if x == nil {
return nil
}
leftInfo := process(x.left)
rightInfo := process(x.right)
// x 1)只有x 2）x往左扎 3）x往右扎
maxPathSumFromHead := x.val
if leftInfo != nil {
maxPathSumFromHead = getMax(maxPathSumFromHead, x.val+leftInfo.maxPathSumFromHead)
}
if rightInfo != nil {
maxPathSumFromHead = getMax(maxPathSumFromHead, x.val+rightInfo.maxPathSumFromHead)
}
// x整棵树最大路径和 1) 只有x 2)左树整体的最大路径和 3) 右树整体的最大路径和
maxPathSum := x.val
if leftInfo != nil {
maxPathSum = getMax(maxPathSum, leftInfo.maxPathSum)
}
if rightInfo != nil {
maxPathSum = getMax(maxPathSum, rightInfo.maxPathSum)
}
// 4) x只往左扎 5）x只往右扎
maxPathSum = getMax(maxPathSumFromHead, maxPathSum)
// 6）一起扎
if leftInfo != nil && rightInfo != nil && leftInfo.maxPathSumFromHead > 0 && rightInfo.maxPathSumFromHead > 0 {
maxPathSum = getMax(maxPathSum, leftInfo.maxPathSumFromHead+rightInfo.maxPathSumFromHead+x.val)
}
return NewInfo(maxPathSum, maxPathSumFromHead)
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
// 如果要返回路径的做法
func getMaxSumPath(head *TreeNode) []*TreeNode {
ans := make([]*TreeNode, 0)
if head != nil {
data := f(head)
fmap := make(map[*TreeNode]*TreeNode)
fmap[head] = head
fatherMap(head, fmap)
fillPath(fmap, data.from, data.to, &ans)
}
return ans
}
type Data struct {
maxAllSum int
from *TreeNode
to *TreeNode
maxHeadSum int
end *TreeNode
}
func NewData(a int, b *TreeNode, c *TreeNode, d int, e *TreeNode) *Data {
res := &Data{}
res.maxAllSum = a
res.from = b
res.to = c
res.maxHeadSum = d
res.end = e
return res
}
func f(x *TreeNode) *Data {
if x == nil {
return nil
}
l := f(x.left)
r := f(x.right)
maxHeadSum := x.val
end := x
if l != nil && l.maxHeadSum > 0 && (r == nil || l.maxHeadSum > r.maxHeadSum) {
maxHeadSum += l.maxHeadSum
end = l.end
}
if r != nil && r.maxHeadSum > 0 && (l == nil || r.maxHeadSum > l.maxHeadSum) {
maxHeadSum += r.maxHeadSum
end = r.end
}
maxAllSum := math.MinInt64
var from *TreeNode
var to *TreeNode
if l != nil {
maxAllSum = l.maxAllSum
from = l.from
to = l.to
}
if r != nil && r.maxAllSum > maxAllSum {
maxAllSum = r.maxAllSum
from = r.from
to = r.to
}
p3 := x.val
if l != nil && l.maxHeadSum > 0 {
p3 = x.val + l.maxHeadSum
}
if p3 > maxAllSum {
maxAllSum = p3
from = x
if l != nil && l.maxHeadSum > 0 {
from = l.end
}
to = x
if r != nil && r.maxHeadSum > 0 {
to = r.end
}
}
return NewData(maxAllSum, from, to, maxHeadSum, end)
}
func fatherMap(h *TreeNode, map0 map[*TreeNode]*TreeNode) {
if h.left == nil && h.right == nil {
return
}
if h.left != nil {
map0[h.left] = h
fatherMap(h.left, map0)
}
if h.right != nil {
map0[h.right] = h
fatherMap(h.right, map0)
}
}
func fillPath(fmap map[*TreeNode]*TreeNode, a *TreeNode, b *TreeNode, ans *[]*TreeNode) {
if a == b {
*ans = append(*ans, a)
} else {
ap := make(map[*TreeNode]struct{})
cur := a
for cur != fmap[cur] {
ap[cur] = struct{}{}
cur = fmap[cur]
}
ap[cur] = struct{}{}
cur = b
var lca *TreeNode
for lca == nil {
if _, ok := ap[cur]; ok {
lca = cur
} else {
cur = fmap[cur]
}
}
for a != lca {
*ans = append(*ans, a)
a = fmap[a]
}
*ans = append(*ans, lca)
right := make([]*TreeNode, 0)
for b != lca {
right = append(right, b)
b = fmap[b]
}
for i := len(right) - 1; i >= 0; i-- {
*ans = append(*ans, right[i])
}
}
}执行结果如下：
