687.Longest Univalue Path
===

###### tags: `Medium`,`Tree`,`DFS`
[687. Longest Univalue Path](https://leetcode.com/problems/longest-univalue-path/)

### 題目描述
Given the root of a binary tree, return 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 the path** between two nodes is represented by the number of edges between them.

##### Example 1:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

##### Example 2:

Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 4).

##### Constraints:
* The number of nodes in the tree is in the range [0, 104].
* -1000 <= Node.val <= 1000
* The depth of the tree will not exceed 1000.

### 解答
#### Python

# 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 __init__(self):
        self.mx = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        
        def dfs(root: Optional[TreeNode], num: int) -> int:
            if not root: return 0
            
            l = dfs(root.left, root.val)
            r = dfs(root.right, root.val)
            
            self.mx = l + r if l + r > self.mx else self.mx
            
            return 0 if root.val != num else 1 + max(l, r)
        
        dfs(root, root.val)
        
        return self.mx

> [name=Kobe Bryant] [time=Nov 25, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)