Python, with simple explanation via DFS


  • -1

    Each path in a binary tree has a root node i.e., path members are all children of one unique node in the path.
    Based on this property, for every node n as a root, we obtain left and right consecutive paths increasing upto node n (referenced via li and ri) and decreasing upto node n (ld and rd) and satisfying the consecutive property at node n. We update the the maximum consecutive path length by comparing the running maximum with the consecutive path length with node n as root.

    class Solution(object):
        def longestConsecutive(self, root):
            if not root: return 0
            m=[1]
            def longest(node):
                li,ld,ri,rd=0,0,0,0
                if node.left is not None:
                    (x,y)=longest(node.left)
                    if node.val-node.left.val==1: (li,ld)=(x,0)
                    elif node.val-node.left.val==-1: (li,ld)=(0,y)
    
                if node.right is not None:
                    (x,y)=longest(node.right)
                    if node.val-node.right.val==1: (ri,rd)=(x,0)
                    elif node.val-node.right.val==-1: (ri,rd)=(0,y)
                m.append(max(li+rd+1,ri+ld+1))
                return max(li,ri)+1,max(ld,rd)+1
    
            longest(root)
            return max(m)
                
                
                
            
    

Log in to reply
 

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