Python solution with detailed explanation


  • 0
    G

    Solution

    Binary Tree Longest Consecutive Sequence https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

    Bottom Up (Postfix) O(N) Approach

    • Maintain a global variable to track the maximum path so far.
    • Use bottom up approach to return the consecutive sequence count from both left and right nodes.
    class Solution(object):
        def longestConsecutive(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.max_so_far = 0
            self.helper(root)
            return self.max_so_far
        
        def helper(self, root):
            if root == None:
                return 0
            max_l, max_r = self.helper(root.left), self.helper(root.right)
            max_curr = 1
            if root.left and root.left.val == root.val+1:
                max_curr = max(max_curr, max_l+1)
            if root.right and root.right.val == root.val+1:
                max_curr = max(max_curr, max_r+1)
            self.max_so_far = max(max_curr, self.max_so_far)
            return max_curr
    

    Top Down (Prefix) O(N) Approach

    • Maintain a prev variable which tracks the value of the previous variable.
    • Maintain a so_far variable that tracks the count of the current run.
    • Update or reset so_far to 1 depending on if current and prev node satisfy the constraint.
    class Solution(object):
        def longestConsecutive(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            so_far, self.max_so_far, prev = 0, 0, None
            self.helper(root, so_far, prev)
            return self.max_so_far
        
        def helper(self, root, so_far, prev):
            if root == None:
                return
            elif (prev == None) or (prev+1 == root.val):
                self.max_so_far = max(self.max_so_far, so_far+1)
                so_far = so_far+1
            else:
                so_far = 1
            self.helper(root.left, so_far, root.val)
            self.helper(root.right, so_far, root.val)
            return
    

Log in to reply
 

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