# Tree - 687. Longest Univalue Path

687. Longest Univalue Path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

```              5
/ \
4   5
/ \   \
1   1   5```

Output: 2

Example 2:

Input:

```              1
/ \
4   5
/ \   \
4   4   5```

Output: 2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

go：

```/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func longestUnivaluePath(root *TreeNode) int {
if root == nil {
return 0
}

var res int
univaluePath(root, &res)

return res
}

func univaluePath(node *TreeNode, res *int) int {
if node == nil {
return 0
}

leftLen := univaluePath(node.Left, res)
rightLen := univaluePath(node.Right, res)

var leftPathLen, rightPathLen int
if node.Left != nil && node.Val == node.Left.Val {
leftPathLen = leftLen + 1
}
if node.Right != nil && node.Val == node.Right.Val {
rightPathLen = rightLen + 1
}

*res = max(*res, leftPathLen + rightPathLen)

return max(leftPathLen, rightPathLen)

}

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

return j
}```

0 条评论

• ### Tree - 298. Binary Tree Longest Consecutive Sequence

298 . Binary Tree Longest Consecutive Sequence

• ### Array - 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from th...

• ### Tree - 124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

• ### 2017 Multi-University Training Contest - Team 9 1001&&HDU 6161 Big binary tree【树形dp+hash】

Big binary tree Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65...

• ### Tree - 298. Binary Tree Longest Consecutive Sequence

298 . Binary Tree Longest Consecutive Sequence

• ### Code Forces 652C Foe Pairs

C. Foe Pairs time limit per test 1 second memory limit per test 256 megaby...

• ### HDUOJ----Eddy's research I

Eddy's research I Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

• ### 算法分析设计--递归算法

定义： 程序直接或间接调用自身的编程技巧称为递归算法（Recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型...

• ### Leercode 35 Search Insert Position

Given a sorted array and a target value, return the index if the target is foun...