104. Maximum Depth of Binary Tree

Problem Statement

link: https://leetcode.com/problems/maximum-depth-of-binary-tree/ https://leetcode.cn/problems/maximum-depth-of-binary-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.

Example:

Input: root = [3,9,20,null,null,15,7] Output: 3

Input: root = [1,null,2] Output: 2

Solution Approach

The solution leverages breadth-first search (BFS) to traverse each level of the binary tree and calculate its depth.

Algorithm

1. Initialize a queue with the root node and set the result (res) to 0.
2. For each iteration, process all nodes currently in the queue, simultaneously adding their left and right children to a temporary list (tmp).
3. Replace the main queue with tmp and increment the res by 1 until the queue is empty, signifying that all tree levels have been processed.

Implement

    class Solution:
      def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        q = [root]
        res = 0
        while q:
            tmp = []
            for n in q:
                if n.left:
                    tmp.append(n.left)
                if n.right:
                    tmp.append(n.right)
            q = tmp
            res += 1
        return res    

 

    
    

Twitter  facebook  Email