Python DFS Non-recursive

  • 0
    class Solution(object):
        def longestConsecutive(self, root):
            if not root: return 0
            # The stack contains the current node, the parent's value, and 
            # the current accumulator. For the root node, it doesn't matter 
            # what the previous value is, because if it's not root.val-1, we will
            # assume 1, and if it happens to be root.val-1, we will increment 
            # the accumulator by 1
            st = [(root, 0, 0)]
            # Max accumulator found
            M = 0
            while st:
                node, par, c = st.pop()
                if not node: continue
                if node.val-par == 1:
                    c = c+1
                    c = 1
                M = max(M, c)
                st.append((node.left, node.val, c))
                st.append((node.right, node.val, c))
            return M

Log in to reply

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