687. 最长同值路径

题目描述：

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例 1：

输入：root = [5,4,5,1,1,5] 
输出：2

示例 2：

输入：root = [1,4,5,4,4,5] 
输出：2

提示：

• 树的节点数的范围是 [0, 10^4]
• -1000 <= Node.val <= 1000
• 树的深度将不超过 1000

---

解题分析及思路：

思路：

使用变量 ans 保存最长同值路径长度。

我们对根结点进行深度优先搜索，对于当前搜索的结点 root，我们分别获取它左结点的最长同值有向路径长度 left，右结点的最长同值有向路径长度 right。

• 如果结点 root 的左结点非空且结点 root 的值与它的左结点的值相等，那么结点 root 的左最长同值有向路径长度 left=left+1，否则 left =0

• 如果结点 root 的右结点非空且结点 root 的值与它的右结点的值相等，那么结点 root 的右最长同值有向路径长度 right=right+1，否则 right =0。

令 ans=max(ans,left +right)，并且返回结点 root 对应的最长同值有向路径长度 max(left ,right)。

func longestUnivaluePath(root *TreeNode) (ans int) {
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		l, r := dfs(node.Left), dfs(node.Right)
		if node.Left != nil && node.Left.Val == node.Val {
			l = l + 1
		} else {
			l = 0
		}
		if node.Right != nil && node.Right.Val == node.Val {
			r = r + 1
		} else {
			r = 0
		}
		ans = max(ans, l+r)
		return max(l, r)
	}
	dfs(root)
	return
}

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

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:55 ms,击败了93.83% 的Go用户
• 内存消耗：7.3 MB,击败了93.28% 的Go用户