A plain BFS solution in Python


  • 0
    K

    Google likes to wrap a classic data structure or an algorithm with a fancy package.
    As you read through the problem, you are expected to peel the onion and see what is the real candy inside --- think abstractly.
    This capability, of course, is contingent on a good understanding of these fundamental computational elements.
    Particularly, in this problem, you are asked to maintain a counter as you traverse a binary tree. Then, is recursion the best way to maintain a counter? Here, I just use a plain BFS to solve it.

    class Solution(object):
        def longestConsecutive(self, root):
            """
            USE BFS, as the problem is about the comparison between children and parent layers.
            """
            
            if not root:
                return 0
            cnt = 1
            queue = [(root,cnt)]
            ret = 1
            while queue:
                node,cnt = queue.pop(0)
                if node.left:
                    newcnt = cnt + 1 if node.left.val==node.val+1 else 1
                    ret = max(newcnt,ret)
                    queue.append((node.left,newcnt))
                if node.right:
                    newcnt = cnt + 1 if node.right.val==node.val+1 else 1
                    ret = max(newcnt,ret)
                    queue.append((node.right,newcnt))
            return ret
    

Log in to reply
 

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