Dado el recorrido previo al pedido de un árbol de búsqueda binario. Luego, la tarea es imprimir los Nodes de hoja del árbol de búsqueda binaria del pedido previo dado.
Ejemplos:
Input : preorder[] = {890, 325, 290, 530, 965};
Output : 290 530 965
Tree represented is,
890
/ \
325 965
/ \
290 530
Input : preorder[] = { 3, 2, 4 };
Output : 2 4
En esta publicación, se discute una solución recursiva simple. La idea es usar dos variables mínimas y máximas y tomar i (índice en la array de entrada), el índice para la array de pedido anticipado dada, y crear recursivamente el Node raíz y, en consecuencia, verificar si la izquierda y la derecha existen o no. Este método devuelve una variable booleana, y si tanto la izquierda como la derecha son falsas, simplemente significa que la izquierda y la derecha son nulas, por lo tanto, debe ser un Node hoja, así que imprímalo allí y devuelva verdadero como raíz en ese índice.
C++
// Recursive C++ program to find leaf
// nodes from given preorder traversal
#include<bits/stdc++.h>
using namespace std;
// Print the leaf node from
// the given preorder of BST.
bool isLeaf(int pre[], int &i, int n,
int min, int max)
{
if (i >= n)
return false;
if (pre[i] > min && pre[i] < max) {
i++;
bool left = isLeaf(pre, i, n, min, pre[i-1]);
bool right = isLeaf(pre, i, n, pre[i-1], max);
if (!left && !right)
cout << pre[i-1] << " ";
return true;
}
return false;
}
void printLeaves(int preorder[], int n)
{
int i = 0;
isLeaf(preorder, i, n, INT_MIN, INT_MAX);
}
// Driver code
int main()
{
int preorder[] = { 890, 325, 290, 530, 965 };
int n = sizeof(preorder)/sizeof(preorder[0]);
printLeaves(preorder, n);
return 0;
}
Java
// Recursive Java program to find leaf
// nodes from given preorder traversal
class GFG
{
static int i = 0;
// Print the leaf node from
// the given preorder of BST.
static boolean isLeaf(int pre[], int n,
int min, int max)
{
if (i >= n)
{
return false;
}
if (pre[i] > min && pre[i] < max)
{
i++;
boolean left = isLeaf(pre, n, min, pre[i - 1]);
boolean right = isLeaf(pre, n, pre[i - 1], max);
if (!left && !right)
{
System.out.print(pre[i - 1] + " ");
}
return true;
}
return false;
}
static void printLeaves(int preorder[], int n)
{
isLeaf(preorder, n, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
// Driver code
public static void main(String[] args)
{
int preorder[] = {890, 325, 290, 530, 965};
int n = preorder.length;
printLeaves(preorder, n);
}
}
// This code contributed by Rajput-Ji
Python3
# Recursive Python program to find leaf # nodes from given preorder traversal # Print the leaf node from # the given preorder of BST. def isLeaf(pre, i, n, Min, Max): if i[0] >= n: return False if pre[i[0]] > Min and pre[i[0]] < Max: i[0] += 1 left = isLeaf(pre, i, n, Min, pre[i[0] - 1]) right = isLeaf(pre, i, n, pre[i[0] - 1], Max) if left == False and right == False: print(pre[i[0] - 1], end = " ") return True return False def printLeaves(preorder, n): i = [0] INT_MIN, INT_MAX = -999999999999, 999999999999 isLeaf(preorder, i, n, INT_MIN, INT_MAX) # Driver code if __name__ == '__main__': preorder = [890, 325, 290, 530, 965] n = len(preorder) printLeaves(preorder, n) # This code is contributed by PranchalK
C#
// Recursive C# program to find leaf
// nodes from given preorder traversal
using System;
class GFG
{
static int i = 0;
// Print the leaf node from
// the given preorder of BST.
static bool isLeaf(int []pre, int n,
int min, int max)
{
if (i >= n)
{
return false;
}
if (pre[i] > min && pre[i] < max)
{
i++;
bool left = isLeaf(pre, n, min, pre[i - 1]);
bool right = isLeaf(pre, n, pre[i - 1], max);
if (!left && !right)
{
Console.Write(pre[i - 1] + " ");
}
return true;
}
return false;
}
static void printLeaves(int []preorder, int n)
{
isLeaf(preorder, n, int.MinValue, int.MaxValue);
}
// Driver code
public static void Main(String[] args)
{
int []preorder = {890, 325, 290, 530, 965};
int n = preorder.Length;
printLeaves(preorder, n);
}
}
// This code is contributed by princiraj1992
PHP
<?php
// Recursive PHP program to
// find leaf nodes from given
// preorder traversal
// Print the leaf node from
// the given preorder of BST.
function isLeaf($pre, &$i, $n,
$min, $max)
{
if ($i >= $n)
return false;
if ($pre[$i] > $min &&
$pre[$i] < $max)
{
$i++;
$left = isLeaf($pre, $i, $n,
$min, $pre[$i - 1]);
$right = isLeaf($pre, $i, $n,
$pre[$i - 1], $max);
if (!$left && !$right)
echo $pre[$i - 1] , " ";
return true;
}
return false;
}
function printLeaves($preorder, $n)
{
$i = 0;
isLeaf($preorder, $i, $n,
PHP_INT_MIN, PHP_INT_MAX);
}
// Driver code
$preorder = array (890, 325, 290,
530, 965 );
$n = sizeof($preorder);
printLeaves($preorder, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Recursive Javascript program to find leaf
// nodes from given preorder traversal
let i = 0;
// Print the leaf node from
// the given preorder of BST.
function isLeaf(pre, n, min, max)
{
if (i >= n)
{
return false;
}
if (pre[i] > min && pre[i] < max)
{
i++;
let left = isLeaf(pre, n, min, pre[i - 1]);
let right = isLeaf(pre, n, pre[i - 1], max);
if (!left && !right)
{
document.write(pre[i - 1] + " ");
}
return true;
}
return false;
}
function printLeaves(preorder, n)
{
isLeaf(preorder, n, Number.MIN_VALUE,
Number.MAX_VALUE);
}
// Driver code
let preorder = [ 890, 325, 290, 530, 965 ];
let n = preorder.length;
printLeaves(preorder, n);
// This code is contributed by divyeshrabadiya07
</script>
Producción :
290 530 965
Publicación traducida automáticamente
Artículo escrito por vishal22091998 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA