case 3 ans = max(ans, 2 + up(root.left, root.right))
返回 max(up(root.left), up(root.right)) + 1
题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
self.ans = 0
if root is None:
return self.ans
self.univaluePath(node=root)
return self.ans
def univaluePath(self, node):
if node is None:
return 0
l = self.univaluePath(node.left)
r = self.univaluePath(node.right)
pl, pr = 0, 0
if node.left and node.left.val == node.val:
pl = l + 1
if node.right and node.right.val == node.val:
pr = r + 1
self.ans = max(self.ans, pl + pr)
return max(pl, pr)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
self.res = 1
self.helper(root)
return self.res - 1 if self.res >= 2 else 0
def helper(self, root):
if root is None:
# [长度，该长度的值]
return [0, 0]
l = self.helper(root.left)
r = self.helper(root.right)
temp_l, temp_r = 0, 0
if l[0] != 0 and l[1] == root.val:
temp_l += l[0]
if r[0] != 0 and r[1] == root.val:
temp_r += r[0]
self.res = max(self.res, temp_l + temp_r + 1)
return [max(temp_r, temp_l)+1, root.val]
