题目描述
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
解法
不妨定义findMax函数表示每个节点的最长单边路径值（所谓单边路径，即当前节点与左子树节点构成的路径，或当前节点与右子树节点构成的路径），根据某一个节点的左子节点findMax值，和右子节点findMax值，即可获得当前节点的同值路径。则遍历二叉树对每个节点的左右子节点求出findMax值，即可获得该二叉树中的最大同值路径。
class Solution(object):
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ret=0
def findMax(root):
if not root:
return 0
llen=findMax(root.left)
rlen=findMax(root.right)
llen=llen+1 if root.left and root.left.val==root.val else 0
rlen=rlen+1 if root.right and root.right.val==root.val else 0
self.ret=max(self.ret,llen+rlen)
return max(llen,rlen)
findMax(root)
return self.ret
