Stack Based (non-recursive) solution


  • 2
    W

    I remember someone once saying that anything you can do with recursion can be done faster with a stack. So I figured I'ld be a rebel and use a stack here instead of a recursive method in an attempt to penny pinch on the overhead...
    It clocked 188 ms. VIVA LA STACK!

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def longestConsecutive(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            
            if (not root):
                return 0;
                
            tempNode=root
            nodeStack=[]
            nodeStack.append(tempNode)
            maxPathLength=1
            lengthStack=[]
            lengthStack.append(1)
            while(len(nodeStack) > 0):
                tempNode=nodeStack.pop()
                tempLength=lengthStack.pop()
                if (tempLength > maxPathLength):
                    maxPathLength=tempLength
                if (tempNode.left):
                    nodeStack.append(tempNode.left)
                    if (tempNode.left.val == (1+tempNode.val)):
                        lengthStack.append(tempLength+1)
                    else:
                        lengthStack.append(1)
                if (tempNode.right):
                    nodeStack.append(tempNode.right)
                    if (tempNode.right.val == (1+tempNode.val)):
                        lengthStack.append(tempLength+1)
                    else:
                        lengthStack.append(1)
            
            return maxPathLength

Log in to reply
 

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