forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlongest-univalue-path.py
More file actions
23 lines (19 loc) · 828 Bytes
/
longest-univalue-path.py
File metadata and controls
23 lines (19 loc) · 828 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def longestUnivaluePath(self, root):
def getUnivalueLength(node, val):
if not node: return 0
l, r = getUnivalueLength(node.left, node.val), getUnivalueLength(node.right, node.val)
self.ans = max(self.ans, l+r)
if node.val==val: return 1+max(l, r)
return 0
if not root: return 0
self.ans = float('-inf')
getUnivalueLength(root, root.val)
return self.ans
"""
The main I idea is simple.
Traverse all the node.
Each node, we assume that the longestUnivaluePath will pass through it.
So we can update the `self.ans` if `l+r` is larger.
At the same time, `getUnivalueLength()` will return the max length of the path (start from itself) which has the value `val`.
"""