• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
int longestConsecutive(TreeNode* root) {
if (!root)
return 0;
return dfs(root, root->val, 0, 0);
}

private:
int dfs(TreeNode* root, int target, int length, int maxLength) {
if (!root)
return maxLength;
if (root->val == target)
maxLength = max(maxLength, ++length);
else
length = 1;
return max(dfs(root->left, root->val + 1, length, maxLength),
dfs(root->right, root->val + 1, length, maxLength));
}
};
``````

## JAVA

``````class Solution {
public int longestConsecutive(TreeNode root) {
if (root == null)
return 0;
return dfs(root, -1, 0, 1);
}

private int dfs(TreeNode root, int target, int length, int max) {
if (root == null)
return max;
if (root.val == target)
max = Math.max(max, ++length);
else
length = 1;
return Math.max(dfs(root.left, root.val + 1, length, max),
dfs(root.right, root.val + 1, length, max));
}
}
``````

## Python

``````class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
if not root:
return 0

def dfs(root: Optional[TreeNode], target: int, length: int, maxLength: int) -> int:
if not root:
return maxLength
if root.val == target:
length += 1
maxLength = max(maxLength, length)
else:
length = 1
return max(dfs(root.left, root.val + 1, length, maxLength),
dfs(root.right, root.val + 1, length, maxLength))

return dfs(root, root.val, 0, 0)
``````