Dado un árbol binario, encuentre su profundidad mínima. La profundidad mínima es el número de Nodes a lo largo del camino más corto desde el Node raíz hasta el Node hoja más cercano.
Por ejemplo, la altura mínima debajo del árbol binario es 2.
C++
// C++ program to find minimum depth of a given Binary Tree
#include<bits/stdc++.h>
using namespace std;
// A BT Node
struct Node
{
int data;
struct Node* left, *right;
};
int minDepth(Node *root)
{
// Corner case. Should never be hit unless the code is
// called on root = NULL
if (root == NULL)
return 0;
// Base case : Leaf Node. This accounts for height = 1.
if (root->left == NULL && root->right == NULL)
return 1;
int l = INT_MAX, r = INT_MAX;
// If left subtree is not NULL, recur for left subtree
if (root->left)
l = minDepth(root->left);
// If right subtree is not NULL, recur for right subtree
if (root->right)
r = minDepth(root->right);
//height will be minimum of left and right height +1
return min(l , r) + 1;
}
// Utility function to create new Node
Node *newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
// Driver program
int main()
{
// Let us construct the Tree shown in the above figure
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout <<"The minimum depth of binary tree is : "<< minDepth(root);
return 0;
}
C
// C program to find minimum depth of a given Binary Tree
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// A BT Node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
int minDepth(Node* root)
{
// Corner case. Should never be hit unless the code is
// called on root = NULL
if (root == NULL)
return 0;
// Base case : Leaf Node. This accounts for height = 1.
if (root->left == NULL && root->right == NULL)
return 1;
int l = INT_MAX;
int r = INT_MIN;
// If left subtree is not NULL, recur for left subtree
if (root->left)
l = minDepth(root->left);
// If right subtree is not NULL, recur for right subtree
if (root->right)
r = minDepth(root->right);
// height will be minimum of left and right height +1
return min(l, r) + 1;
}
// Utility function to create new Node
Node* newNode(int data)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
// Driver program
int main()
{
// Let us construct the Tree shown in the above figure
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("The minimum depth of binary tree is : %d",
minDepth(root));
return 0;
}
// This code is contributed by aditya kumar (adityakumar129)
Java
/* Java implementation to find minimum depth
of a given Binary tree */
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
//Root of the Binary Tree
Node root;
int minimumDepth()
{
return minimumDepth(root);
}
/* Function to calculate the minimum depth of the tree */
int minimumDepth(Node root)
{
// Corner case. Should never be hit unless the code is
// called on root = NULL
if (root == null)
return 0;
// Base case : Leaf Node. This accounts for height = 1.
if (root.left == null && root.right == null)
return 1;
// If left subtree is NULL, recur for right subtree
if (root.left == null)
return minimumDepth(root.right) + 1;
// If right subtree is NULL, recur for left subtree
if (root.right == null)
return minimumDepth(root.left) + 1;
return Math.min(minimumDepth(root.left),
minimumDepth(root.right)) + 1;
}
/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The minimum depth of "+
"binary tree is : " + tree.minimumDepth());
}
}
Python3
# Python program to find minimum depth of a given Binary Tree # Tree node class Node: def __init__(self , key): self.data = key self.left = None self.right = None def minDepth(root): # Corner Case.Should never be hit unless the code is # called on root = NULL if root is None: return 0 # Base Case : Leaf node.This accounts for height = 1 if root.left is None and root.right is None: return 1 # If left subtree is Null, recur for right subtree if root.left is None: return minDepth(root.right)+1 # If right subtree is Null , recur for left subtree if root.right is None: return minDepth(root.left) +1 return min(minDepth(root.left), minDepth(root.right))+1 # Driver Program root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print (minDepth(root)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
/* C# implementation to find minimum depth
of a given Binary tree */
/* Class containing left and right child of current
node and key value*/
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
//Root of the Binary Tree
public Node root;
public virtual int minimumDepth()
{
return minimumDepth(root);
}
/* Function to calculate the minimum depth of the tree */
public virtual int minimumDepth(Node root)
{
// Corner case. Should never be hit unless the code is
// called on root = NULL
if (root == null)
{
return 0;
}
// Base case : Leaf Node. This accounts for height = 1.
if (root.left == null && root.right == null)
{
return 1;
}
// If left subtree is NULL, recur for right subtree
if (root.left == null)
{
return minimumDepth(root.right) + 1;
}
// If right subtree is NULL, recur for left subtree
if (root.right == null)
{
return minimumDepth(root.left) + 1;
}
return Math.Min(minimumDepth(root.left), minimumDepth(root.right)) + 1;
}
/* Driver program to test above functions */
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
Console.WriteLine("The minimum depth of binary tree is : " + tree.minimumDepth());
}
}
// This code is contributed by Shrikant13
Javascript
<script>
/* javascript implementation to find minimum depth
of a given Binary tree */
/* Class containing left and right child of current
node and key value*/
class Node {
constructor(item) {
this.data = item;
this.left = this.right = null;
}
}
// Root of the Binary Tree
let root;
function minimumDepth() {
return minimumDepth(root);
}
/* Function to calculate the minimum depth of the tree */
function minimumDepth( root) {
// Corner case. Should never be hit unless the code is
// called on root = NULL
if (root == null)
return 0;
// Base case : Leaf Node. This accounts for height = 1.
if (root.left == null && root.right == null)
return 1;
// If left subtree is NULL, recur for right subtree
if (root.left == null)
return minimumDepth(root.right) + 1;
// If right subtree is NULL, recur for left subtree
if (root.right == null)
return minimumDepth(root.left) + 1;
return Math.min(minimumDepth(root.left), minimumDepth(root.right)) + 1;
}
/* Driver program to test above functions */
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("The minimum depth of "
+ "binary tree is : " + minimumDepth(root));
// This code contributed by aashish1995
</script>
C++
// C++ program to find minimum depth of a given Binary Tree
#include<bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// A queue item (Stores pointer to node and an integer)
struct qItem
{
Node *node;
int depth;
};
// Iterative method to find minimum depth of Binary Tree
int minDepth(Node *root)
{
// Corner Case
if (root == NULL)
return 0;
// Create an empty queue for level order traversal
queue<qItem> q;
// Enqueue Root and initialize depth as 1
qItem qi = {root, 1};
q.push(qi);
// Do level order traversal
while (q.empty() == false)
{
// Remove the front queue item
qi = q.front();
q.pop();
// Get details of the remove item
Node *node = qi.node;
int depth = qi.depth;
// If this is the first leaf node seen so far
// Then return its depth as answer
if (node->left == NULL && node->right == NULL)
return depth;
// If left subtree is not NULL, add it to queue
if (node->left != NULL)
{
qi.node = node->left;
qi.depth = depth + 1;
q.push(qi);
}
// If right subtree is not NULL, add it to queue
if (node->right != NULL)
{
qi.node = node->right;
qi.depth = depth+1;
q.push(qi);
}
}
return 0;
}
// Utility function to create a new tree Node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree shown in above diagram
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << minDepth(root);
return 0;
}
Java
// Java program to find minimum depth
// of a given Binary Tree
import java.util.*;
class GFG
{
// A binary Tree node
static class Node
{
int data;
Node left, right;
}
// A queue item (Stores pointer to
// node and an integer)
static class qItem
{
Node node;
int depth;
public qItem(Node node, int depth)
{
this.node = node;
this.depth = depth;
}
}
// Iterative method to find
// minimum depth of Binary Tree
static int minDepth(Node root)
{
// Corner Case
if (root == null)
return 0;
// Create an empty queue for level order traversal
Queue<qItem> q = new LinkedList<>();
// Enqueue Root and initialize depth as 1
qItem qi = new qItem(root, 1);
q.add(qi);
// Do level order traversal
while (q.isEmpty() == false)
{
// Remove the front queue item
qi = q.peek();
q.remove();
// Get details of the remove item
Node node = qi.node;
int depth = qi.depth;
// If this is the first leaf node seen so far
// Then return its depth as answer
if (node.left == null && node.right == null)
return depth;
// If left subtree is not null,
// add it to queue
if (node.left != null)
{
qi.node = node.left;
qi.depth = depth + 1;
q.add(qi);
}
// If right subtree is not null,
// add it to queue
if (node.right != null)
{
qi.node = node.right;
qi.depth = depth + 1;
q.add(qi);
}
}
return 0;
}
// Utility function to create a new tree Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver Code
public static void main(String[] args)
{
// Let us create binary tree shown in above diagram
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
System.out.println(minDepth(root));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to find minimum depth of a given Binary Tree
# A Binary Tree node
class Node:
# Utility to create new node
def __init__(self , data):
self.data = data
self.left = None
self.right = None
def minDepth(root):
# Corner Case
if root is None:
return 0
# Create an empty queue for level order traversal
q = []
# Enqueue root and initialize depth as 1
q.append({'node': root , 'depth' : 1})
# Do level order traversal
while(len(q)>0):
# Remove the front queue item
queueItem = q.pop(0)
# Get details of the removed item
node = queueItem['node']
depth = queueItem['depth']
# If this is the first leaf node seen so far
# then return its depth as answer
if node.left is None and node.right is None:
return depth
# If left subtree is not None, add it to queue
if node.left is not None:
q.append({'node' : node.left , 'depth' : depth+1})
# if right subtree is not None, add it to queue
if node.right is not None:
q.append({'node': node.right , 'depth' : depth+1})
# Driver program to test above function
# Lets construct a binary tree shown in above diagram
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print (minDepth(root))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to find minimum depth
// of a given Binary Tree
using System;
using System.Collections.Generic;
class GFG
{
// A binary Tree node
public class Node
{
public int data;
public Node left, right;
}
// A queue item (Stores pointer to
// node and an integer)
public class qItem
{
public Node node;
public int depth;
public qItem(Node node, int depth)
{
this.node = node;
this.depth = depth;
}
}
// Iterative method to find
// minimum depth of Binary Tree
static int minDepth(Node root)
{
// Corner Case
if (root == null)
return 0;
// Create an empty queue for
// level order traversal
Queue<qItem> q = new Queue<qItem>();
// Enqueue Root and initialize depth as 1
qItem qi = new qItem(root, 1);
q.Enqueue(qi);
// Do level order traversal
while (q.Count != 0)
{
// Remove the front queue item
qi = q.Peek();
q.Dequeue();
// Get details of the remove item
Node node = qi.node;
int depth = qi.depth;
// If this is the first leaf node
// seen so far.
// Then return its depth as answer
if (node.left == null &&
node.right == null)
return depth;
// If left subtree is not null,
// add it to queue
if (node.left != null)
{
qi.node = node.left;
qi.depth = depth + 1;
q.Enqueue(qi);
}
// If right subtree is not null,
// add it to queue
if (node.right != null)
{
qi.node = node.right;
qi.depth = depth + 1;
q.Enqueue(qi);
}
}
return 0;
}
// Utility function to create a new tree Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver Code
public static void Main(String[] args)
{
// Let us create binary tree
// shown in above diagram
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
Console.WriteLine(minDepth(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find minimum depth
// of a given Binary Tree
class Node
{
// Utility function to create a new tree Node
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
class qItem
{
constructor(node,depth)
{
this.node = node;
this.depth = depth;
}
}
function minDepth(root)
{
// Corner Case
if (root == null)
return 0;
// Create an empty queue for
// level order traversal
let q = [];
// Enqueue Root and initialize depth as 1
let qi = new qItem(root, 1);
q.push(qi);
// Do level order traversal
while (q.length != 0)
{
// Remove the front queue item
qi = q.shift();
// Get details of the remove item
let node = qi.node;
let depth = qi.depth;
// If this is the first leaf node seen so far
// Then return its depth as answer
if (node.left == null && node.right == null)
return depth;
// If left subtree is not null,
// add it to queue
if (node.left != null)
{
qi.node = node.left;
qi.depth = depth + 1;
q.push(qi);
}
// If right subtree is not null,
// add it to queue
if (node.right != null)
{
qi.node = node.right;
qi.depth = depth + 1;
q.push(qi);
}
}
return 0;
}
// Driver Code
// Let us create binary tree shown
// in above diagram
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write(minDepth(root));
// This code is contributed by rag2127
</script>
C++
/* C++ implementation to find minimum depth
of a given Binary tree */
#include <iostream>
#include<math.h>
using namespace std;
struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int k){
data = k;
left = right = NULL;
}
};
/* Function to calculate the minimum depth of the tree */
int minimumDepth(Node *root, int level)
{
if (root == NULL)
return level;
level++;
return min(minimumDepth(root->left, level),
minimumDepth(root->right, level));
}
/* Driver program to test above functions */
int main()
{
// Let us create binary tree shown in above diagram
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << minimumDepth(root, 0);
return 0;
}
// This code is contributed by aafreen1804.
Java
/* Java implementation to find minimum depth
of a given Binary tree */
/* Class containing left and right child of current
Node and key value*/
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class MinimumTreeHeight {
// Root of the Binary Tree
Node root;
int minimumDepth() { return minimumDepth(root, 0); }
/* Function to calculate the minimum depth of the tree
*/
int minimumDepth(Node root, int level)
{
if (root == null)
return level;
level++;
return Math.min(minimumDepth(root.left, level),
minimumDepth(root.right, level));
}
/* Driver program to test above functions */
public static void main(String args[])
{
MinimumTreeHeight tree = new MinimumTreeHeight();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The minimum depth of "
+ "binary tree is : "
+ tree.minimumDepth());
}
}
Python3
# Python implementation to find minimum depth
# of a given Binary tree
# Class containing left and right child of current
# Node and key value
class Node:
# Constructor to create a new node
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Function to calculate the minimum depth of the tree
def minimumDepth(root, level):
if (root == None):
return level;
level += 1;
return min(minimumDepth(root.left, level),
minimumDepth(root.right, level))
# Driver program to test above functions
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("The minimum depth of ","binary tree is : ", minimumDepth(root, 0))
# This code is contributed by ab2127
C#
/* C# implementation to find minimum depth
of a given Binary tree */
using System;
/* Class containing left and
right child of current
Node and key value*/
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class MinimumTreeHeight {
// Root of the Binary Tree
Node root;
int minimumDepth() { return minimumDepth(root, 0); }
/* Function to calculate the
minimum depth of the tree */
int minimumDepth(Node root, int level)
{
if (root == null)
return level;
level++;
return Math.Min(minimumDepth(root.left, level),
minimumDepth(root.right, level));
}
/* Driver code */
public static void Main(String[] args)
{
MinimumTreeHeight tree = new MinimumTreeHeight();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
Console.WriteLine("The minimum depth of "
+ "binary tree is : "
+ tree.minimumDepth());
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
/* Javascript implementation to find minimum depth
of a given Binary tree */
/* Class containing left and right child of current
Node and key value*/
class Node
{
constructor(item)
{
this.data=item;
this.left=this.right=null;
}
}
// Root of the Binary Tree
let root;
/* Function to calculate the minimum depth of the tree
*/
function minimumDepths()
{
return minimumDepth(root, 0);
}
function minimumDepth(root,level)
{
if (root == null)
return level;
level++;
return Math.min(minimumDepth(root.left, level),
minimumDepth(root.right, level));
}
/* Driver program to test above functions */
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("The minimum depth of "
+ "binary tree is : "
+ minimumDepths());
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA