Dado un árbol binario , la tarea es verificar si consiste en valores de Node dispuestos en orden estrictamente creciente en niveles pares y estrictamente decreciente en niveles impares ( suponiendo que el Node raíz esté en el nivel 0 ).
Ejemplos:
Aporte:
2 / \ 6 3 / \ \ 4 7 11 / \ \ 10 5 1Salida: SÍ
Explicación:
En el nivel 1 (impar), los valores de Node 6 y 3 están en orden estrictamente decreciente.
En el nivel 2 (par), los valores de Node 4, 7 y 11 están en orden estrictamente creciente.
En el nivel 3 (impar), los valores de Node 10, 5 y 1) están en orden estrictamente decreciente.
Por lo tanto, el árbol satisface las condiciones dadas.Aporte:
5 / \ 6 3 / \ \ 4 9 2Salida : NO
Enfoque: la idea es realizar un recorrido de orden de nivel en el árbol binario dado y, para cada nivel, verificar si cumple con las condiciones dadas o no. Siga los pasos a continuación para resolver el problema:
- Cree una cola vacía para almacenar los Nodes de cada nivel uno por uno durante el recorrido del orden de nivel del árbol.
- Empuje el Node raíz a la cola.
- Iterar hasta que la cola esté vacía y realizar lo siguiente:
- Siga extrayendo Nodes del nivel actual de la cola e insértelos en una Arraylist . Empuje todos sus Nodes secundarios a la Cola .
- Si el nivel es par, verifique si los elementos presentes en el Arraylist están en orden creciente o no . Si se determina que es cierto, continúe con el siguiente nivel. De lo contrario , imprima No.
- Del mismo modo, verifique los niveles impares.
- Después de recorrer completamente el árbol, si se encuentra que todos los niveles satisfacen las condiciones, imprima SÍ .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int val;
Node *left, *right;
};
struct Node* newNode(int data)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->val = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Function to check if given binary
// tree satisfies the required conditions
bool checkEvenOddLevel(Node *root)
{
if (root == NULL)
return true;
// Queue to store nodes
// of each level
queue<Node*> q;
q.push(root);
// Stores the current
// level of the binary tree
int level = 0;
// Traverse until the
// queue is empty
while (q.empty())
{
vector<int> vec;
// Stores the number of nodes
// present in the current level
int size = q.size();
for(int i = 0; i < size; i++)
{
Node *node = q.front();
vec.push_back(node->val);
// Insert left and right child
// of node into the queue
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
// If the level is even
if (level % 2 == 0)
{
// If the nodes in this
// level are in strictly
// increasing order or not
for(int i = 0; i < vec.size() - 1; i++)
{
if (vec[i + 1] > vec[i])
continue;
return false;
}
}
// If the level is odd
else if (level % 2 == 1)
{
// If the nodes in this
// level are in strictly
// decreasing order or not
for(int i = 0; i < vec.size() - 1; i++)
{
if (vec[i + 1] < vec[i])
continue;
return false;
}
}
// Increment the level count
level++;
}
return true;
}
// Driver Code
int main()
{
// Construct a Binary Tree
Node *root = NULL;
root = newNode(2);
root->left = newNode(6);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(7);
root->right->right = newNode(11);
root->left->left->left = newNode(10);
root->left->left->right = newNode(5);
root->left->right->right = newNode(1);
// Function Call
if (checkEvenOddLevel(root))
cout << "YES";
else
cout << "NO";
}
// This code is contributed by ipg2016107
Java
// Java Program for the above approach
import java.util.*;
class GFG {
// Structure of Tree node
static class Node {
int val;
Node left, right;
}
// Function to create new Tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = null;
temp.right = null;
return temp;
}
// Function to check if given binary
// tree satisfies the required conditions
public static boolean
checkEvenOddLevel(Node root)
{
if (root == null)
return true;
// Queue to store nodes
// of each level
Queue<Node> q
= new LinkedList<>();
q.add(root);
// Stores the current
// level of the binary tree
int level = 0;
// Traverse until the
// queue is empty
while (!q.isEmpty()) {
ArrayList<Integer> list
= new ArrayList<>();
// Stores the number of nodes
// present in the current level
int size = q.size();
for (int i = 0; i < size; i++) {
Node node = q.poll();
list.add(node.val);
// Insert left and right child
// of node into the queue
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
// If the level is even
if (level % 2 == 0) {
// If the nodes in this
// level are in strictly
// increasing order or not
for (int i = 0; i < list.size() - 1;
i++) {
if (list.get(i + 1) > list.get(i))
continue;
return false;
}
}
// If the level is odd
else if (level % 2 == 1) {
// If the nodes in this
// level are in strictly
// decreasing order or not
for (int i = 0; i < list.size() - 1;
i++) {
if (list.get(i + 1) < list.get(i))
continue;
return false;
}
}
// Increment the level count
level++;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
// Construct a Binary Tree
Node root = null;
root = newNode(2);
root.left = newNode(6);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(7);
root.right.right = newNode(11);
root.left.left.left = newNode(10);
root.left.left.right = newNode(5);
root.left.right.right = newNode(1);
// Function Call
if (checkEvenOddLevel(root)) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
Python3
# Python3 program for the above approach
# Tree node
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.val = data
# Function to return new tree node
def newNode(data):
temp = Node(data)
return temp
# Function to check if the
# tree is even-odd tree
def checkEvenOddLevel(root):
if (root == None):
return True
q = []
# Stores nodes of each level
q.append(root)
# Store the current level
# of the binary tree
level = 0
# Traverse until the
# queue is empty
while (len(q) != 0):
l = []
# Stores the number of nodes
# present in the current level
size = len(q)
for i in range(size):
node = q[0]
q.pop(0)
# Insert left and right child
# of node into the queue
if (node.left != None):
q.append(node.left);
if (node.right != None):
q.append(node.right);
# If the level is even
if (level % 2 == 0):
# If the nodes in this
# level are in strictly
# increasing order or not
for i in range(len(l) - 1):
if (l[i + 1] > l[i]):
continue
return False
# If the level is odd
elif (level % 2 == 1):
# If the nodes in this
# level are in strictly
# decreasing order or not
for i in range(len(l) - 1):
if (l[i + 1] < l[i]):
continue
return False
# Increment the level count
level += 1
return True
# Driver code
if __name__=="__main__":
# Construct a Binary Tree
root = None
root = newNode(2)
root.left = newNode(6)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(7)
root.right.right = newNode(11)
root.left.left.left = newNode(10)
root.left.left.right = newNode(5)
root.left.right.right = newNode(1)
# Check if the binary tree
# is even-odd tree or not
if (checkEvenOddLevel(root)):
print("YES")
else:
print("NO")
# This code is contributed by rutvik_56
C#
// C# Program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of Tree node
public class Node
{
public int val;
public Node left, right;
}
// Function to create
// new Tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = null;
temp.right = null;
return temp;
}
// Function to check if given binary
// tree satisfies the required conditions
public static bool checkEvenOddLevel(Node root)
{
if (root == null)
return true;
// Queue to store nodes
// of each level
Queue<Node> q =
new Queue<Node>();
q.Enqueue(root);
// Stores the current
// level of the binary tree
int level = 0;
// Traverse until the
// queue is empty
while (q.Count != 0)
{
List<int> list =
new List<int>();
// Stores the number of nodes
// present in the current level
int size = q.Count;
for (int i = 0; i < size; i++)
{
Node node = q.Dequeue();
list.Add(node.val);
// Insert left and right child
// of node into the queue
if (node.left != null)
q.Enqueue(node.left);
if (node.right != null)
q.Enqueue(node.right);
}
// If the level is even
if (level % 2 == 0)
{
// If the nodes in this
// level are in strictly
// increasing order or not
for (int i = 0;
i < list.Count - 1; i++)
{
if (list[i + 1] > list[i])
continue;
return false;
}
}
// If the level is odd
else if (level % 2 == 1)
{
// If the nodes in this
// level are in strictly
// decreasing order or not
for (int i = 0;
i < list.Count - 1; i++)
{
if (list[i + 1] < list[i])
continue;
return false;
}
}
// Increment the level count
level++;
}
return true;
}
// Driver Code
public static void Main(String[] args)
{
// Construct a Binary Tree
Node root = null;
root = newNode(2);
root.left = newNode(6);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(7);
root.right.right = newNode(11);
root.left.left.left = newNode(10);
root.left.left.right = newNode(5);
root.left.right.right = newNode(1);
// Function Call
if (checkEvenOddLevel(root))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Structure of Tree node
class Node
{
constructor(data)
{
this.left = null;
this.right = null;
this.val = data;
}
}
// Function to create new Tree node
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Function to check if given binary
// tree satisfies the required conditions
function checkEvenOddLevel(root)
{
if (root == null)
return true;
// Queue to store nodes
// of each level
let q = [];
q.push(root);
// Stores the current
// level of the binary tree
let level = 0;
// Traverse until the
// queue is empty
while (q.length > 0)
{
let list = [];
// Stores the number of nodes
// present in the current level
let size = q.length;
for(let i = 0; i < size; i++)
{
let node = q[0];
q.shift();
list.push(node.val);
// Insert left and right child
// of node into the queue
if (node.left != null)
q.push(node.left);
if (node.right != null)
q.push(node.right);
}
// If the level is even
if (level % 2 == 0)
{
// If the nodes in this
// level are in strictly
// increasing order or not
for(let i = 0; i < list.length - 1; i++)
{
if (list[i + 1] > list[i])
continue;
return false;
}
}
// If the level is odd
else if (level % 2 == 1)
{
// If the nodes in this
// level are in strictly
// decreasing order or not
for(let i = 0; i < list.length - 1; i++)
{
if (list[i + 1] < list[i])
continue;
return false;
}
}
// Increment the level count
level++;
}
return true;
}
// Driver code
// Construct a Binary Tree
let root = null;
root = newNode(2);
root.left = newNode(6);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(7);
root.right.right = newNode(11);
root.left.left.left = newNode(10);
root.left.left.right = newNode(5);
root.left.right.right = newNode(1);
// Function Call
if (checkEvenOddLevel(root))
{
document.write("YES");
}
else
{
document.write("NO");
}
// This code is contributed by suresh07
</script>
Producción:
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lavishgarg26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA