111. Minimum Depth of Binary Tree
1. Description
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.
2. Note
- A leaf is a node with no children.
3. Example
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
4. Constraints
- The number of nodes in the tree is in the range [0, $10^5$].
- -1000 <= Node.val <= 1000
5. Solutions
My Accepted Solution
n is the number of nodes in the tree
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// int minDepth(TreeNode* root)
int minDepth(TreeNode *i_root)
{
if(!i_root) return 0;
if(!i_root->left && !i_root->right) return 1;
int leftChildDepth = minDepth(i_root->left);
int rightChildDepth = minDepth(i_root->right);
return min(leftChildDepth == 0 ? INT_MAX : leftChildDepth
, rightChildDepth == 0 ? INT_MAX : rightChildDepth)
+ 1;
}
};
5.1 Breadth-first Search
n is the number of nodes in the tree
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// int minDepth(TreeNode* root)
int minDepth(TreeNode *i_root)
{
if(!i_root) return 0;
int result = 1;
queue<TreeNode *> currentLevelNodes{{i_root}};
queue<TreeNode *> nextLevelNodes;
while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
{
if(currentLevelNodes.empty())
{
result++;
swap(currentLevelNodes, nextLevelNodes);
}
else
{
auto node = currentLevelNodes.front();
currentLevelNodes.pop();
if(!node->left && !node->right) return result;
if(node->left) nextLevelNodes.push(node->left);
if(node->right) nextLevelNodes.push(node->right);
}
}
return result;
}
};