A plain BFS solution in Python

  • 0

    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)
                if node.right:
                    newcnt = cnt + 1 if node.right.val==node.val+1 else 1
                    ret = max(newcnt,ret)
            return ret

Log in to reply

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