# 298. Binary Tree Longest Consecutive Sequence

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int longestConsecutive(TreeNode* root) { if (root == nullptr) return 0; return dfs(root, root->val, 0, 0); } private: int dfs(TreeNode* root, int target, int length, int maxLength) { if (root == nullptr) 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)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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)); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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)