Why so much high runtime for DFS? If anyone can please explain.


  • 0
    P

    Because recursive solution is straightforward, I experimented with DFS. Popping last element is supposed to O(1) and the rest of logic is just traversing the tree. It shows I beat only 7-8% of submissions. Not able to understand, why.

    class Solution(object):
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0 
            queue = [root]
            ls = [1]
            maxheight = 0 
            while queue:
                node = queue.pop()
                val = ls.pop() 
                if not node.left and not node.right:
                    maxheight = max(maxheight,val) 
                if node.left:
                    queue.append(node.left)
                    ls.append(val+1)
                if node.right:
                    queue.append(node.right)
                    ls.append(val+1)
            return maxheight 
    
    

Log in to reply
 

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