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.
# 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