Skip to content

Latest commit

 

History

History
44 lines (33 loc) · 1.02 KB

111.Minimum-Depth-of-Binary-Tree.md

File metadata and controls

44 lines (33 loc) · 1.02 KB

111. Minimum Depth of Binary Tree

Difficulty: Easy

URL

https://leetcode.com/problems/minimum-depth-of-binary-tree/

Solution

Approach 1: Level Order Traversal

The run time for this approach is asynptotically less than $O(n)$.

The code is shown below:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        depth = 0
        if not root:
            return 0
        
        q = deque([root])
        while q:
            size = len(q)
            depth += 1
            for _ in range(size):
                node = q.popleft()
                if not node.left and not node.right:
                    return depth
                if node.left:   q.append(node.left)
                if node.right:  q.append(node.right)
                    
        return depth