[leetcode] binary tree longest consecutive sequence

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.

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class :
    """
    @param root: the root of binary tree
    @return: the length of the longest consecutive sequence path
    """
    def longestConsecutive(self, root):
        
        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

[leetcode] binary tree longest consecutive sequence

近期文章

近期评论

标签

热门

文章归档

分类目录

功能