Leetcode 549 Solution
This article provides solution to leetcode question 549 (binary-tree-longest-consecutive-sequence-ii)
Access this page by simply typing in "lcs 549" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii
Solution
# 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 longestConsecutive(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
def dfs(node, last_val, diff):
if not node:
return 0
if last_val is not None and last_val - node.val != diff:
return 0
left = dfs(node.left, node.val, diff)
right = dfs(node.right, node.val, diff)
return max(left, right) + 1
ans = dfs(root, None, 1) + dfs(root, None, -1) - 1
return max(
ans,
self.longestConsecutive(root.left),
self.longestConsecutive(root.right),
)