104. Maximum Depth of Binary Tree

• categories: Code, Interview Question, leetcode, Easy
• source: https://leetcode.com/problems/maximum-depth-of-binary-tree/description
• topics: Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Breadth-first search

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        depth = 0
        nodes = [root]
 
        if not root:
            return 0
        
        while nodes:
            new_nodes = []
            depth += 1
            while nodes:
                node = nodes.pop()
                if node.left:
                    new_nodes.append(node.left)
                if node.right:
                    new_nodes.append(node.right)
            nodes.extend(new_nodes)
                
        return depth

Depth-first search

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(
            self.maxDepth(root.left),
            self.maxDepth(root.right))