Binary Tree Longest Consecutive Sequence

Problem Id: 298 Difficulty: Medium Tag: Tree


Intuition

This is a basic problem of DFS with one additional variables.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        self.longestlength = 0
        self._dfs(root, float('inf'), 0)
        return self.longestlength

    def _dfs(self, node, parent, length):
        if node is None:
            return

        if parent + 1 == node.val:
            length += 1
        else:
            length = 1
        self.longestlength = max(length, self.longestlength)
        self._dfs(node.left, node.val, length)
        self._dfs(node.right, node.val, length)