Dado un árbol binario, averigüe la profundidad del Node de hoja de nivel impar más profundo. Tome el nivel de raíz como profundidad 1.
Ejemplos:
Input :
Output : 5
Input : 10
/ \
28 13
/ \
14 15
/ \
23 24
Output : 3
Podemos atravesar el árbol comenzando desde el nivel raíz y mantener curr_level del Node.
Incrementa el curr_level cada vez que vamos a un subárbol izquierdo o derecho.
Devuelve la profundidad máxima de un nivel impar, si existe.
Algoritmo:
1) return 0 if curr_node == NULL
2) if curr_node is leaf and curr_level is odd,
return curr_level
3) else maximum(depthOdd(left subtree),
depthOdd(right subtree))
A continuación se muestra la implementación.
C++
// C++ program to find depth of the deepest
// odd level node
#include<bits/stdc++.h>
using namespace std;
// A Tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Utility function which
// returns whether the current node
// is a leaf or not
bool isleaf(Node *curr_node)
{
return (curr_node->left == NULL &&
curr_node->right == NULL);
}
// function to return the longest
// odd level depth if it exists
// otherwise 0
int deepestOddLevelDepthUtil(Node *curr_node, int curr_level)
{
// Base case
// return from here
if ( curr_node == NULL)
return 0;
// increment current level
curr_level += 1;
// if curr_level is odd
// and its a leaf node
if ( curr_level % 2 != 0 && isleaf(curr_node))
return curr_level;
return max(deepestOddLevelDepthUtil(curr_node->left,curr_level),
deepestOddLevelDepthUtil(curr_node->right,curr_level));
}
// A wrapper over deepestOddLevelDepth()
int deepestOddLevelDepth(Node *curr_node)
{
return deepestOddLevelDepthUtil(curr_node, 0);
}
// Driver code
int main()
{
/* 10
/ \
28 13
/ \
14 15
/ \
23 24
Let us create Binary Tree shown in above example */
Node *root = newNode(10);
root->left = newNode(28);
root->right = newNode(13);
root->right->left = newNode(14);
root->right->right = newNode(15);
root->right->right->left = newNode(23);
root->right->right->right = newNode(24);
cout << deepestOddLevelDepth(root) << endl;
return 0;
}
Java
// Java program to find depth of the deepest
// odd level node
class GfG {
// A Tree node
static class Node
{
int key;
Node left, right;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return (temp);
}
// Utility function which
// returns whether the current node
// is a leaf or not
static boolean isleaf(Node curr_node)
{
return (curr_node.left == null && curr_node.right == null);
}
// function to return the longest
// odd level depth if it exists
// otherwise 0
static int deepestOddLevelDepthUtil(Node curr_node, int curr_level)
{
// Base case
// return from here
if ( curr_node == null)
return 0;
// increment current level
curr_level += 1;
// if curr_level is odd
// and its a leaf node
if ( curr_level % 2 != 0 && isleaf(curr_node))
return curr_level;
return Math.max(deepestOddLevelDepthUtil(curr_node.left,curr_level),
deepestOddLevelDepthUtil(curr_node.right,curr_level));
}
// A wrapper over deepestOddLevelDepth()
static int deepestOddLevelDepth(Node curr_node)
{
return deepestOddLevelDepthUtil(curr_node, 0);
}
public static void main(String[] args)
{
/* 10
/ \
28 13
/ \
14 15
/ \
23 24
Let us create Binary Tree shown in above example */
Node root = newNode(10);
root.left = newNode(28);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.right.left = newNode(23);
root.right.right.right = newNode(24);
System.out.println(deepestOddLevelDepth(root));
}
}
Python3
# Python3 program to find depth of # the deepest odd level node # Helper function that allocates a # new node with the given data and # None left and right pointers. class newNode: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Utility function which returns # whether the current node is a # leaf or not def isleaf(curr_node) : return (curr_node.left == None and curr_node.right == None) # function to return the longest # odd level depth if it exists # otherwise 0 def deepestOddLevelDepthUtil(curr_node, curr_level) : # Base case # return from here if (curr_node == None) : return 0 # increment current level curr_level += 1 # if curr_level is odd and # its a leaf node if (curr_level % 2 != 0 and isleaf(curr_node)) : return curr_level return max(deepestOddLevelDepthUtil(curr_node.left, curr_level), deepestOddLevelDepthUtil(curr_node.right, curr_level)) # A wrapper over deepestOddLevelDepth() def deepestOddLevelDepth(curr_node) : return deepestOddLevelDepthUtil(curr_node, 0) # Driver Code if __name__ == '__main__': """ 10 / \ 28 13 / \ 14 15 / \ 23 24 Let us create Binary Tree shown in above example """ root = newNode(10) root.left = newNode(28) root.right = newNode(13) root.right.left = newNode(14) root.right.right = newNode(15) root.right.right.left = newNode(23) root.right.right.right = newNode(24) print(deepestOddLevelDepth(root)) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to find depth of the deepest
// odd level node
using System;
class GfG
{
// A Tree node
class Node
{
public int key;
public Node left, right;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return (temp);
}
// Utility function which
// returns whether the current node
// is a leaf or not
static bool isleaf(Node curr_node)
{
return (curr_node.left == null &&
curr_node.right == null);
}
// function to return the longest
// odd level depth if it exists
// otherwise 0
static int deepestOddLevelDepthUtil(Node curr_node,
int curr_level)
{
// Base case
// return from here
if ( curr_node == null)
return 0;
// increment current level
curr_level += 1;
// if curr_level is odd
// and its a leaf node
if ( curr_level % 2 != 0 && isleaf(curr_node))
return curr_level;
return Math.Max(deepestOddLevelDepthUtil(curr_node.left,curr_level),
deepestOddLevelDepthUtil(curr_node.right,curr_level));
}
// A wrapper over deepestOddLevelDepth()
static int deepestOddLevelDepth(Node curr_node)
{
return deepestOddLevelDepthUtil(curr_node, 0);
}
public static void Main(String[] args)
{
/* 10
/ \
28 13
/ \
14 15
/ \
23 24
Let us create Binary Tree shown in above example */
Node root = newNode(10);
root.left = newNode(28);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.right.left = newNode(23);
root.right.right.right = newNode(24);
Console.WriteLine(deepestOddLevelDepth(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find depth of the deepest
// odd level node
// A Tree node
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
}
// Utility function to create a new node
function newNode(key)
{
var temp = new Node();
temp.key = key;
temp.left = null;
temp.right = null;
return (temp);
}
// Utility function which
// returns whether the current node
// is a leaf or not
function isleaf(curr_node)
{
return (curr_node.left == null &&
curr_node.right == null);
}
// function to return the longest
// odd level depth if it exists
// otherwise 0
function deepestOddLevelDepthUtil(curr_node, curr_level)
{
// Base case
// return from here
if ( curr_node == null)
return 0;
// increment current level
curr_level += 1;
// if curr_level is odd
// and its a leaf node
if ( curr_level % 2 != 0 && isleaf(curr_node))
return curr_level;
return Math.max(deepestOddLevelDepthUtil(curr_node.left,curr_level),
deepestOddLevelDepthUtil(curr_node.right,curr_level));
}
// A wrapper over deepestOddLevelDepth()
function deepestOddLevelDepth(curr_node)
{
return deepestOddLevelDepthUtil(curr_node, 0);
}
/* 10
/ \
28 13
/ \
14 15
/ \
23 24
Let us create Binary Tree shown in above example */
var root = newNode(10);
root.left = newNode(28);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.right.left = newNode(23);
root.right.right.right = newNode(24);
document.write(deepestOddLevelDepth(root));
</script>
Producción
3
Este artículo es una contribución de Shubham Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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