Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/111.html
111 Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
@tag-tree
Algorithm
DFS
The pitfall
is, if a node has a child on the left and a null on the right, how to deal with it. In this case, the node is not a leaf, and we must continue to look for it. This time, we directly judge the root situation. Divided into left and right, or only left and right, return directly.
- First, it is judged to be empty. If the current node does not exist, return 0 directly.
- Then see if the left child node does not exist, then call the recursive function on the right child node and add 1 to return.
- Similarly, if the right child node does not exist, call the recursive function on the left child node and add 1 to return.
- If both left and right child nodes exist, call the recursive function on the left and right child nodes respectively, and return the smaller value of the two by adding 1
BFS
BFS traversal, recording the number of layers traversed, once the first leaf node
is traversed, the current number of layers is returned, which is the minimum depth of the binary tree, if (!node->left && !node->right) return ans;
.
Code
Java
-
public class Minimum_Depth_of_Binary_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // @note: key is how to handle null child node public class Solution_recursion { public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; // leaf } if (root.left == null) { return 1 + minDepth(root.right); } if (root.right == null) { return 1 + minDepth(root.left); } return 1 + Math.min(minDepth(root.left), minDepth(root.right)); } } }
-
// OJ: https://leetcode.com/problems/minimum-depth-of-binary-tree/ // Time: O(N) // Space: O(N) class Solution { public: int minDepth(TreeNode* root) { if (!root) return 0; queue<TreeNode*> q; q.push(root); int ans = 1; while (q.size()) { int cnt = q.size(); while (cnt--) { auto node = q.front(); q.pop(); if (!node->left && !node->right) return ans; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } ++ans; } return -1; } };
-
# 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 class Solution: def minDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 if root.left is None: return 1 + self.minDepth(root.right) if root.right is None: return 1 + self.minDepth(root.left) return 1 + min(self.minDepth(root.left), self.minDepth(root.right)) ############ # 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 class Solution: def minDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 if root.left is None: return 1 + self.minDepth(root.right) if root.right is None: return 1 + self.minDepth(root.left) return 1 + min(self.minDepth(root.left), self.minDepth(root.right)) ########## # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def minDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 left = self.minDepth(root.left) right = self.minDepth(root.right) if not left and not right: return 1 elif not left: return right + 1 elif not right: return left + 1 else: return min(left, right) + 1