2021-10-11：二叉树中的最大路径和。路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一

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])
        }
    }
}