Easy Python Beats 90% with Explaination


  • 1
    W
    class Solution(object):
    def longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return self.helper(root, -1.2345 ,1)
        
        
    def helper(self, root, val, count):
        if not root:
            return count
        if root.val == val + 1:
            return max(self.helper(root.left, root.val, count + 1), self.helper(root.right, root.val, count + 1))
        else:
            return max(count, self.helper(root.left, root.val, 1), self.helper(root.right, root.val, 1))
    

    To calculate the longest consecutive length, we obviously need more parameters than provided in the original longestConsecutive function.
    The val parameter is there to track the last tree node value and the count variable keeps track of how many consecutive values we've seen so far.
    Again, let recursion do the job. We just need to think about two cases:

    1. value is one more than val. We pass count + 1 to left and right child and find the max of them.
    2. value is not one more than val. In this case, we reset count to 1, and also remember to put the previous count into the max function.

    We just call helper in the longestConsecutive function. The value -1.2345 does not have any meaning. I just chose it randomly to make sure that it does not the first node start with count = 1.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.