[LeetCode] Binary Tree Longest Consecutive Sequence

leetcode

This problem is the first of its series.
The initial thought might be from each node, check the consecutive sequence starting from itself. However, this will result in TLE because it’s O(n) time complexity.
How can we improve? We don’t actually need to recalculate for each node.
We only need to keep track of the current length of this consecutive sequence. When we see a new node, if it’s +1 to previous value, we add one to length; otherwise, we reset length to 1. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the length of the longest consecutive sequence path
    """
    def longestConsecutive(self, root):
        # write your code here
        self.ans = 0
        def DFS(node, depth, parent):
            if not node:
                self.ans = max(self.ans, depth)
                return
            if parent:
                if node.val == parent.val + 1:
                    depth += 1
                    self.ans = max(self.ans, depth)
                else:
                    self.ans = max(self.ans, depth)
                    depth = 1

            DFS(node.left, depth, node)
            DFS(node.right, depth, node)

        DFS(root, 1, None)
        return self.ans