November 17, 2021: the longest path of the same value. Given a binary tree, find the longest path

2021-11-17： The longest path of the same value . Given a binary tree , Find the longest path , Each node in this path has the same value . This path may or may not go through the root node . Be careful ： The path length between two nodes is represented by the number of sides between them . Power button 687.

answer 2021-11-17：

recursive .

1.x irrelevant , The left maximum path and the right maximum path take the maximum value .

1. x of . 2.1. x own . 2.2. Left （x）+x+ Right （x）.

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    root := NewTreeNode(5)
    root.left = NewTreeNode(4)
    root.right = NewTreeNode(5)
    root.left.left = NewTreeNode(1)
    root.left.right = NewTreeNode(1)
    root.right.right = NewTreeNode(5)
    ret := longestUnivaluePath(root)
    fmt.Println(ret)
}

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func NewTreeNode(v int) *TreeNode {
    ret := &TreeNode{}
    ret.val = v
    return ret

}

func longestUnivaluePath(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return process(root).max - 1
}

//  Construction to x A tree headed by nodes , Return two messages 
type Info struct {

    //  On one path ： Each node is required to pass only once 
    len int //  The path must be from x When you start and can only go down , The maximum distance of the path 
    max int //  The path does not require that it must be from x In the case of departure , The maximum legal path distance of the whole tree 
}

func NewInfo(l, m int) *Info {
    ret := &Info{}
    ret.len = l
    ret.max = m
    return ret
}

func process(x *TreeNode) *Info {
    if x == nil {
        return NewInfo(0, 0)
    }
    l := x.left
    r := x.right
    //  On the left tree , It is not required to start from the left child , Maximum path 
    //  On the left tree , We must start from the left child , The maximum path down 
    linfo := process(l)
    //  On the right tree , Don't ask to start from the right child , Maximum path 
    //  On the right tree , We must start from the right child , The maximum path down 
    rinfo := process(r)
    //  Must be from x In the case of departure , The maximum path down 
    len0 := 1
    if l != nil && l.val == x.val {
        len0 = linfo.len + 1
    }
    if r != nil && r.val == x.val {
        len0 = getMax(len0, rinfo.len+1)
    }
    //  Not required from x set out , Maximum path 
    max := getMax(getMax(linfo.max, rinfo.max), len0)
    if l != nil && r != nil && l.val == x.val && r.val == x.val {
        max = getMax(max, linfo.len+rinfo.len+1)
    }
    return NewInfo(len0, max)
}

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

The results are as follows ：

picture

Zuo Shen java Code