LONGEST UNIVALUE PATH | LEETCODE 687 | PYTHON DFS SOLUTION
Vložit
- čas přidán 24. 07. 2024
- Channel Discord Community: / discord
Problem Link: leetcode.com/problems/longest...
Today we are solving yet another of these postorder DFS problems where we need to do some computations after traversing to the children nodes. It's Longest Univalue Path (Leetcode 687). Luckily we've solved a lot of these types of questions before so this one shouldn't be that much harder.
TIMESTAMPS
00:00 Intro
00:07 Question Prompt
00:22 Basic Examples
01:20 Solution Intuition
04:49 Coding
13:10 Time/Space Complexity
14:15 Outro - Věda a technologie
Other simpler implementation is:
def longestUnivaluePath(root: Optional[TreeNode]) -> int:
if not root:
return 0
res = [0]
def helper(node, parent):
if not node:
return 0
left = helper(node.left, node)
right = helper(node.right, node)
res[0] = max(res[0], left + right)
if parent and parent.val == node.val:
return max(left, right) + 1
return 0
helper(root, None)
return res[0]
dang, I had the same code when I was solving it, but the editorial code seems much shorter