Naive python code with simple explanation


  • 0
    T
    class Solution(object):
        def longestConsecutive(self, root):
            return self.rec(root)
    
        def rec(self, p, pre=None):
            """
            return (a,b,c): 
                a for longest increasing length among current and its children
                b for longest path among current and its children
                c for longest decreasing length among current and its children
                
                note: [decreasing|increasing]+current+[increasing|decreasing]
                then check
            """
            if not p:
                return 0, 0, 0
            l = self.rec(p.left, p)
            r = self.rec(p.right, p)
    
            if pre and pre.val == p.val + 1:
                return 0, \
                       max(1 + l[0], 1 + r[0], 1 + l[2], 1 + r[2], l[1], r[1], l[0] + 1 + r[2], r[0] + 1 + l[2]), \
                       1 + max(l[2], r[2])
            elif pre and pre.val == p - 1:
                return 1 + max(l[0], r[0]), \
                       max(1 + l[0], 1 + r[0], 1 + l[2], 1 + r[2], l[1], r[1], l[0] + 1 + r[2], r[0] + 1 + l[2]), \
                       0
            return 0, \
                   max(1 + l[0], 1 + r[0], 1 + l[2], 1 + r[2], l[1], r[1], l[0] + 1 + r[2], r[0] + 1 + l[2]), \
                   0
    
    

Log in to reply
 

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