Binary Tree Longest Consecutive Sequence II

Intuition

This could be done using DFS and DP. In the dfs function, we add 3 additional return value, value, increasing_len and decreasing_len. And we could get the calculate these value of the current node by its left node and right node.

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.longest = 0
        self._dfs(root)
        return self.longest

    def _dfs(self, node):
        if node is None:
            return float('inf'), 0, 0
        l = self._dfs(node.left)
        r = self._dfs(node.right)
        inc_len = max(
            1 + (l[1] if l[0] == node.val - 1 else 0),
            1 + (r[1] if r[0] == node.val - 1 else 0)
        )
        dec_len = max(
            1 + (l[2] if l[0] == node.val + 1 else 0),
            1 + (r[2] if r[0] == node.val + 1 else 0)
        )
        self.longest = max(dec_len + inc_len - 1, self.longest)
        return node.val, inc_len, dec_len