The number of nodes in the tree is in the range [0, 105].
-1000 <= Node.val <= 1000
Solutions
Solution 1: Recursion
The termination condition for recursion is when the current node is null, at which point return $0$. If one of the left or right subtrees of the current node is null, return the minimum depth of the non-null subtree plus $1$. If neither the left nor right subtree of the current node is null, return the smaller value of the minimum depths of the left and right subtrees plus $1$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415
# 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 = rightclassSolution:defminDepth(self,root:Optional[TreeNode])->int:ifrootisNone:return0ifroot.leftisNone:return1+self.minDepth(root.right)ifroot.rightisNone:return1+self.minDepth(root.left)return1+min(self.minDepth(root.left),self.minDepth(root.right))
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcminDepth(root*TreeNode)int{ifroot==nil{return0}ifroot.Left==nil{return1+minDepth(root.Right)}ifroot.Right==nil{return1+minDepth(root.Left)}return1+min(minDepth(root.Left),minDepth(root.Right))}
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */#define min(a, b) (((a) < (b)) ? (a) : (b))intminDepth(structTreeNode*root){if(!root){return0;}if(!root->left){return1+minDepth(root->right);}if(!root->right){return1+minDepth(root->left);}intleft=minDepth(root->left);intright=minDepth(root->right);return1+min(left,right);}
Solution 2: BFS
Use a queue to implement breadth-first search, initially adding the root node to the queue. Each time, take a node from the queue. If this node is a leaf node, directly return the current depth. If this node is not a leaf node, add all non-null child nodes of this node to the queue. Continue to search the next layer of nodes until a leaf node is found.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516171819202122
# 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 = rightclassSolution:defminDepth(self,root:Optional[TreeNode])->int:ifrootisNone:return0q=deque([root])ans=0while1:ans+=1for_inrange(len(q)):node=q.popleft()ifnode.leftisNoneandnode.rightisNone:returnansifnode.left:q.append(node.left)ifnode.right:q.append(node.right)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcminDepth(root*TreeNode)(ansint){ifroot==nil{return0}q:=[]*TreeNode{root}for{ans++forn:=len(q);n>0;n--{node:=q[0]q=q[1:]ifnode.Left==nil&&node.Right==nil{return}ifnode.Left!=nil{q=append(q,node.Left)}ifnode.Right!=nil{q=append(q,node.Right)}}}}