Dado el recorrido de Preorder de un BST, verifique si cada Node que no es hoja tiene solo un hijo. Suponga que el BST contiene entradas únicas.
Ejemplos:
C++
#include<bits/stdc++.h>
using namespace std;
bool hasOnlyOneChild(int pre[], int size)
{
int nextDiff, lastDiff;
for (int i=0; i<size-1; i++)
{
nextDiff = pre[i] - pre[i+1];
lastDiff = pre[i] - pre[size-1];
if (nextDiff*lastDiff < 0)
return false;;
}
return true;
}
// driver program to test above function
int main()
{
int pre[] = {8, 3, 5, 7, 6};
int size = sizeof(pre)/sizeof(pre[0]);
if (hasOnlyOneChild(pre, size) == true )
cout<<"Yes";
else
cout<<"No";
return 0;
}
// This code is contributed by rrrtnx.
C
#include <stdio.h>
bool hasOnlyOneChild(int pre[], int size)
{
int nextDiff, lastDiff;
for (int i=0; i<size-1; i++)
{
nextDiff = pre[i] - pre[i+1];
lastDiff = pre[i] - pre[size-1];
if (nextDiff*lastDiff < 0)
return false;;
}
return true;
}
// driver program to test above function
int main()
{
int pre[] = {8, 3, 5, 7, 6};
int size = sizeof(pre)/sizeof(pre[0]);
if (hasOnlyOneChild(pre, size) == true )
printf("Yes");
else
printf("No");
return 0;
}
Java
// Check if each internal node of BST has only one child
class BinaryTree {
boolean hasOnlyOneChild(int pre[], int size) {
int nextDiff, lastDiff;
for (int i = 0; i < size - 1; i++) {
nextDiff = pre[i] - pre[i + 1];
lastDiff = pre[i] - pre[size - 1];
if (nextDiff * lastDiff < 0) {
return false;
};
}
return true;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int pre[] = new int[]{8, 3, 5, 7, 6};
int size = pre.length;
if (tree.hasOnlyOneChild(pre, size) == true) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Check if each internal
# node of BST has only one child
def hasOnlyOneChild (pre, size):
nextDiff=0; lastDiff=0
for i in range(size-1):
nextDiff = pre[i] - pre[i+1]
lastDiff = pre[i] - pre[size-1]
if nextDiff*lastDiff < 0:
return False
return True
# driver program to
# test above function
if __name__ == "__main__":
pre = [8, 3, 5, 7, 6]
size= len(pre)
if (hasOnlyOneChild(pre,size) == True):
print("Yes")
else:
print("No")
# This code is contributed by
# Harshit Saini
C#
// Check if each internal node of BST has only one child
using System;
public class BinaryTree
{
bool hasOnlyOneChild(int[] pre, int size)
{
int nextDiff, lastDiff;
for (int i = 0; i < size - 1; i++)
{
nextDiff = pre[i] - pre[i + 1];
lastDiff = pre[i] - pre[size - 1];
if (nextDiff * lastDiff < 0)
{
return false;
};
}
return true;
}
// Driver code
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
int []pre = new int[]{8, 3, 5, 7, 6};
int size = pre.Length;
if (tree.hasOnlyOneChild(pre, size) == true)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by aashish1995
Javascript
<script>
// Check if each internal node of BST has only one child
function hasOnlyOneChild(pre, size)
{
var nextDiff, lastDiff;
for (var i = 0; i < size - 1; i++)
{
nextDiff = pre[i] - pre[i + 1];
lastDiff = pre[i] - pre[size - 1];
if (nextDiff * lastDiff < 0)
{
return false;
};
}
return true;
}
// Driver code
var pre = [8, 3, 5, 7, 6];
var size = pre.length;
if (hasOnlyOneChild(pre, size) == true)
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by itsok.
</script>
C++
#include <bits/stdc++.h>
using namespace std;
int hasOnlyOneChild(int pre[], int size)
{
// Initialize min and max using last two elements
int min, max;
if (pre[size - 1] > pre[size - 2])
{
max = pre[size - 1];
min = pre[size - 2];
}
else
{
max = pre[size - 2];
min = pre[size - 1];
}
// Every element must be either smaller
// than min or greater than max
for(int i = size - 3; i >= 0; i--)
{
if (pre[i] < min)
min = pre[i];
else if (pre[i] > max)
max = pre[i];
else
return false;
}
return true;
}
// Driver code
int main()
{
int pre[] = { 8, 3, 5, 7, 6 };
int size = sizeof(pre) / sizeof(pre[0]);
if (hasOnlyOneChild(pre,size))
cout <<"Yes";
else
cout <<"No";
return 0;
}
// This code is contributed by shivanisinghss2110
C
#include <stdio.h>
int hasOnlyOneChild(int pre[], int size)
{
// Initialize min and max using last two elements
int min, max;
if (pre[size-1] > pre[size-2])
{
max = pre[size-1];
min = pre[size-2];
}
else
{
max = pre[size-2];
min = pre[size-1];
}
// Every element must be either smaller than min or
// greater than max
for (int i=size-3; i>=0; i--)
{
if (pre[i] < min)
min = pre[i];
else if (pre[i] > max)
max = pre[i];
else
return false;
}
return true;
}
// Driver program to test above function
int main()
{
int pre[] = {8, 3, 5, 7, 6};
int size = sizeof(pre)/sizeof(pre[0]);
if (hasOnlyOneChild(pre,size))
printf("Yes");
else
printf("No");
return 0;
}
Java
// Check if each internal node of BST has only one child
class BinaryTree {
boolean hasOnlyOneChild(int pre[], int size) {
// Initialize min and max using last two elements
int min, max;
if (pre[size - 1] > pre[size - 2]) {
max = pre[size - 1];
min = pre[size - 2];
} else {
max = pre[size - 2];
min = pre[size - 1];
}
// Every element must be either smaller than min or
// greater than max
for (int i = size - 3; i >= 0; i--) {
if (pre[i] < min) {
min = pre[i];
} else if (pre[i] > max) {
max = pre[i];
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int pre[] = new int[]{8, 3, 5, 7, 6};
int size = pre.length;
if (tree.hasOnlyOneChild(pre, size) == true) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Check if each internal
# node of BST has only one child
# approach 2
def hasOnlyOneChild(pre,size):
# Initialize min and max
# using last two elements
min=0; max=0
if pre[size-1] > pre[size-2] :
max = pre[size-1]
min = pre[size-2]
else :
max = pre[size-2]
min = pre[size-1]
# Every element must be
# either smaller than min or
# greater than max
for i in range(size-3, 0, -1):
if pre[i] < min:
min = pre[i]
elif pre[i] > max:
max = pre[i]
else:
return False
return True
# Driver program to
# test above function
if __name__ == "__main__":
pre = [8, 3, 5, 7, 6]
size = len(pre)
if (hasOnlyOneChild(pre, size)):
print("Yes")
else:
print("No")
# This code is contributed by
# Harshit Saini
C#
// Check if each internal node of BST has only one child
using System;
public class BinaryTree
{
bool hasOnlyOneChild(int []pre, int size)
{
// Initialize min and max using last two elements
int min, max;
if (pre[size - 1] > pre[size - 2]) {
max = pre[size - 1];
min = pre[size - 2];
} else {
max = pre[size - 2];
min = pre[size - 1];
}
// Every element must be either smaller than min or
// greater than max
for (int i = size - 3; i >= 0; i--) {
if (pre[i] < min) {
min = pre[i];
} else if (pre[i] > max) {
max = pre[i];
} else {
return false;
}
}
return true;
}
// Driver code
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
int []pre = new int[]{8, 3, 5, 7, 6};
int size = pre.Length;
if (tree.hasOnlyOneChild(pre, size) == true)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by aashish1995
Javascript
<script>
// Check if each internal node of BST
// has only one child
class BinaryTree {
hasOnlyOneChild(pre, size) {
// Initialize min and max using
// last two elements
var min, max;
if (pre[size - 1] > pre[size - 2]) {
max = pre[size - 1];
min = pre[size - 2];
} else {
max = pre[size - 2];
min = pre[size - 1];
}
// Every element must be either
// smaller than min or
// greater than max
for (var i = size - 3; i >= 0; i--) {
if (pre[i] < min) {
min = pre[i];
} else if (pre[i] > max) {
max = pre[i];
} else {
return false;
}
}
return true;
}
}
// Driver code
var tree = new BinaryTree();
var pre = [8, 3, 5, 7, 6];
var size = pre.length;
if (tree.hasOnlyOneChild(pre, size) == true) {
document.write("Yes");
} else {
document.write("No");
}
</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