Algorithm
Problem Nmae: 111. Minimum Depth of Binary Tree
problem Link: https://leetcode.com/problems/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.
Note: A leaf is a node with no children.
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
Constraints:
- The number of nodes in the tree is in the range
[0, 105]. -1000 <= Node.val <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int minDepth(struct TreeNode *root) {
if (root == NULL)
return 0;
int l = minDepth(root->left);
int r = minDepth(root->right);
if (l == 0 && r == 0) { /* leaf */
return 1;
}
else if (l && r == 0) { /* no right child */
return l + 1;
}
else if (r && l == 0) { /* no left child */
return r + 1;
}
else {
return l < r ? (l + 1) : (r + 1);
}
}
void printTreePreOrder(struct TreeNode *p) {
if (p != NULL) {
printf("%d", p->val);
printTreePreOrder(p->left);
printTreePreOrder(p->right);
}
else printf("#");
}
int main() {
struct TreeNode *t = (struct TreeNode *)calloc(4, sizeof(struct TreeNode));
struct TreeNode *p = t;
p->val = 1;
p->right = ++t;
t->val = 2;
t->right = NULL;
p->right->left = ++t;
t->val = 3;
t->left = NULL;
p->right->left->right = ++t;
t->val = 4;
t->left = t->right = NULL;
printTreePreOrder(p); printf("\n");
/* should be 4 */
printf("%d\n", minDepth(p));
return 0;
}
Input
root = [3,9,20,null,null,15,7]
Output
2
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int l = minDepth(root->left);
int r = minDepth(root->right);
return root->left && root->right ? min(l, r) + 1 : l + r + 1;
}
};
Input
root = [3,9,20,null,null,15,7]
Output
2
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int steps = 1;
Queue < TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
// Level iteration
while (size-- > 0) {
TreeNode removed = queue.remove();
// Leaf reached
if (removed.left == null && removed.right == null) {
return steps;
}
if (removed.left != null) {
queue.add(removed.left);
}
if (removed.right != null) {
queue.add(removed.right);
}
}
steps++;
}
return steps;
}
}
Input
root = [2,null,3,null,4,null,5,null,6]
Output
5
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const minDepth = function(root) {
if(root == null) return 0
if(root.left === null && root.right === null) return 1
const res = {
min:Number.MAX_VALUE
}
dfs(root, res, 1)
return res.min
};
function dfs(node, res, cur) {
if(node == null) return
if(node !== null && node.left === null && node.right === null) {
if(cur < res.min) {
res.min = cur
}
return
}
dfs(node.left, res, cur + 1)
dfs(node.right, res, cur + 1>
}
Input
root = [2,null,3,null,4,null,5,null,6]
Output
5
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.compute(root)
def compute(self, node):
if not node: return 0
left_d=self.compute(node.left)
right_d=self.compute(node.right)
if node.left and node.right: return min(left_d,right_d)+1
else: return max(left_d,right_d)+1
Input
root = [3,9,20,null,null,15,7]
Output
2
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _111_MinimumDepthOfBinaryTree
{
public int MinDepth(TreeNode root)
{
if (root == null) return 0;
if (root.left == null) return MinDepth(root.right) + 1;
if (root.right == null) return MinDepth(root.left) + 1;
return Math.Min(MinDepth(root.left), MinDepth(root.right)) + 1;
}
}
}
Input
root = [3,9,20,null,null,15,7]
Output
2