DFS recursively, DFS iteratively and BFS iteratively in Python


  • 0
    Y
    # 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 maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            # ver 3: BFS iteratively
            queue = collections.deque()
            queue.append((root,0))
            res = 0
            while queue:
                node, level = queue.popleft()
                if not node:
                    res = max(res, level)
                    continue
                queue.append((node.left, level+1))
                queue.append((node.right, level+1))
            return res
            # ver 2: DFS iteratively
            # stack = [(root,0)]
            # res = 0
            # while stack:
            #     node, level = stack.pop()
            #     if not node:
            #         res = max(res, level)
            #         continue
            #     stack.append((node.left, level+1))
            #     stack.append((node.right, level+1))
            # return res
            
        #     # ver 1: DFS recursively
        #     return self.dfs(root)
        # def dfs(self, node):
        #     if not node: return 0
        #     return 1 + max(self.dfs(node.left), self.dfs(node.right))
    

Log in to reply
 

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