题目
难度：★★☆☆☆
类型：二叉树
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意
两个节点之间的路径长度由它们之间的边数表示。
给定的二叉树不超过10000个结点。 树的高度不超过1000。
示例
示例 1
输入:
5
/ \
4 5
/ \ \
1 1 5
输出: 2
示例 2
输入:
1
/ \
4 5
/ \ \
4 4 5
输出: 2
解答
参考大佬博客
class Solution(object):
maxLen = 0
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.getMaxLen(root, root.val)
return self.maxLen
def getMaxLen(self, root, val):
if not root:
return 0
left = self.getMaxLen(root.left, root.val)
right = self.getMaxLen(root.right, root.val)
self.maxLen = max(self.maxLen, left + right)
if root.val == val:
return max(left, right) + 1
return 0
如有疑问或建议，欢迎评论区留言~
