Leetcode 549 Solution

This article provides solution to leetcode question 549 (binary-tree-longest-consecutive-sequence-ii)

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),
        )