549. Binary Tree Longest Consecutive Sequence II (Medium) - TengnanYao/daily_leetcode GitHub Wiki

# 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: TreeNode) -> int:
        # parent helper
        def helper(root, parent):
            if root:
                root.parent = parent
                helper(root.left, root)
                helper(root.right, root)
        helper(root, None)
        def dfs(root, n):
            for node in (root.left, root.right, root.parent):
                if node and node.val - root.val == 1:
                    dfs(node, n + 1)
                else:
                    self.result = max(self.result, n)
        self.result = 0
        q = [root]
        while q:
            node = q.pop(0)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
            for cur in (node.left, node.right, node.parent):
                if cur and node.val - cur.val == 1:
                    break
            else:
                dfs(node, 1)
        return self.result