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
            def longest(node):
                if node.left is not None:
                    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:
                    if node.val-node.right.val==1: (ri,rd)=(x,0)
                    elif node.val-node.right.val==-1: (ri,rd)=(0,y)
                return max(li,ri)+1,max(ld,rd)+1
            return max(m)

Log in to reply

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