Skip to content

Latest commit

 

History

History

111-MinimumDepthofBinaryTree

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

Minimum Depth of Binary Tree

Problem can be found in here!

# 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
def minDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    if not root.left or not root.right:
        return max(minDepth(root.left), minDepth(root.right)) + 1
    else:
        return min(.minDepth(root.left), minDepth(root.right)) + 1

Explanation: We can simply use recursion to solve this problem. There are three cases to handle. First, if we are at the leaf node (root is None), then we can simply return 0. Next, if are not in the leaf node and there is at least one child is None, we should return the depth of the non-empty subtree. For example, if left child is None, we should calculate the depth of right subtree.

Time Complexity: O(n), Space Complexity: O(n)