Dado un árbol binario , la tarea es verificar si el árbol binario es un árbol binario par-impar o no.
Un árbol binario se denomina árbol par-impar cuando todos los Nodes que están en niveles pares tienen valores pares (suponiendo que la raíz está en el nivel 0 ) y todos los Nodes que están en niveles impares tienen valores impares.
Ejemplos:
Aporte:
2 / \ 3 9 / \ \ 4 10 6Salida: SI
Explicación:
Solo el Node en el nivel 0 (par) es 2 (par).
Los Nodes presentes en el nivel 1 son 3 y 9 (ambos impares).
Los Nodes presentes en el nivel 2 son 4, 10 y 6 (todos pares).
Por lo tanto, el árbol binario es un árbol binario par-impar.Aporte:
4 / \ 3 7 / \ \ 4 10 5Salida: NO
Enfoque: siga los pasos a continuación para resolver el problema:
- La idea es realizar un recorrido de orden de niveles y verificar si los Nodes presentes en niveles pares tienen valores pares o no y los Nodes presentes en niveles impares tienen valores impares o no.
- Si se encuentra que algún Node en un nivel impar tiene un valor impar o viceversa, imprima » NO «.
- De lo contrario, después de recorrer completamente el árbol, 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 the
// tree is even-odd tree
bool isEvenOddBinaryTree(Node *root)
{
if (root == NULL)
return true;
// Stores nodes of each level
queue<Node*> q;
q.push(root);
// Store the current level
// of the binary tree
int level = 0;
// Traverse until the
// queue is empty
while (!q.empty())
{
// 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();
// Check if the level
// is even or odd
if (level % 2 == 0)
{
if (node->val % 2 == 1)
return false;
}
else if (level % 2 == 1)
{
if (node->val % 2 == 0)
return true;
}
// Add the nodes of the next
// level into the queue
if (node->left != NULL)
{
q.push(node->left);
}
if (node->right != NULL)
{
q.push(node->right);
}
}
// Increment the level count
level++;
}
return true;
}
// Driver Code
int main()
{
// Construct a Binary Tree
Node *root = NULL;
root = newNode(2);
root->left = newNode(3);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(10);
root->right->right = newNode(6);
// Check if the binary tree
// is even-odd tree or not
if (isEvenOddBinaryTree(root))
cout << "YES";
else
cout << "NO";
}
// This code is contributed by ipg2016107
Java
// Java Program for the above approach
import java.util.*;
class GfG {
// Tree node
static class Node {
int val;
Node left, right;
}
// Function to return 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 the
// tree is even-odd tree
public static boolean
isEvenOddBinaryTree(Node root)
{
if (root == null)
return true;
// Stores nodes of each level
Queue<Node> q
= new LinkedList<>();
q.add(root);
// Store the current level
// of the binary tree
int level = 0;
// Traverse until the
// queue is empty
while (!q.isEmpty()) {
// 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();
// Check if the level
// is even or odd
if (level % 2 == 0) {
if (node.val % 2 == 1)
return false;
}
else if (level % 2 == 1) {
if (node.val % 2 == 0)
return false;
}
// Add the nodes of the next
// level into the queue
if (node.left != null) {
q.add(node.left);
}
if (node.right != null) {
q.add(node.right);
}
}
// 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(3);
root.right = newNode(9);
root.left.left = newNode(4);
root.left.right = newNode(10);
root.right.right = newNode(6);
// Check if the binary tree
// is even-odd tree or not
if (isEvenOddBinaryTree(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 isEvenOddBinaryTree(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):
# Stores the number of nodes
# present in the current level
size = len(q)
for i in range(size):
node = q[0]
q.pop(0)
# Check if the level
# is even or odd
if (level % 2 == 0):
if (node.val % 2 == 1):
return False
elif (level % 2 == 1):
if (node.val % 2 == 0):
return False
# Add the nodes of the next
# level into the queue
if (node.left != None):
q.append(node.left)
if (node.right != None):
q.append(node.right)
# 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(3)
root.right = newNode(9)
root.left.left = newNode(4)
root.left.right = newNode(10)
root.right.right = newNode(6)
# Check if the binary tree
# is even-odd tree or not
if (isEvenOddBinaryTree(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{
// Tree node
class Node
{
public int val;
public Node left, right;
}
// Function to return 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 the
// tree is even-odd tree
static bool isEvenOddBinaryTree(Node root)
{
if (root == null)
return true;
// Stores nodes of each level
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
// Store the current level
// of the binary tree
int level = 0;
// Traverse until the
// queue is empty
while (q.Count != 0)
{
// 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();
// Check if the level
// is even or odd
if (level % 2 == 0)
{
if (node.val % 2 == 1)
return false;
}
else if (level % 2 == 1)
{
if (node.val % 2 == 0)
return false;
}
// Add the nodes of the next
// level into the queue
if (node.left != null)
{
q.Enqueue(node.left);
}
if (node.right != null)
{
q.Enqueue(node.right);
}
}
// 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(3);
root.right = newNode(9);
root.left.left = newNode(4);
root.left.right = newNode(10);
root.right.right = newNode(6);
// Check if the binary tree
// is even-odd tree or not
if (isEvenOddBinaryTree(root))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Tree node
class Node
{
constructor(data)
{
this.left = null;
this.right = null;
this.val = data;
}
}
// Function to return new tree node
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Function to check if the
// tree is even-odd tree
function isEvenOddBinaryTree(root)
{
if (root == null)
return true;
// Stores nodes of each level
let q = [];
q.push(root);
// Store the current level
// of the binary tree
let level = 0;
// Traverse until the
// queue is empty
while (q.length > 0)
{
// 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();
// Check if the level
// is even or odd
if (level % 2 == 0)
{
if (node.val % 2 == 1)
return false;
}
else if (level % 2 == 1)
{
if (node.val % 2 == 0)
return false;
}
// Add the nodes of the next
// level into the queue
if (node.left != null)
{
q.push(node.left);
}
if (node.right != null)
{
q.push(node.right);
}
}
// Increment the level count
level++;
}
return true;
}
// Driver code
// Construct a Binary Tree
let root = null;
root = newNode(2);
root.left = newNode(3);
root.right = newNode(9);
root.left.left = newNode(4);
root.left.right = newNode(10);
root.right.right = newNode(6);
// Check if the binary tree
// is even-odd tree or not
if (isEvenOddBinaryTree(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)
Método 2 (usando la diferencia entre padres e hijos)
Enfoque:
la idea es verificar la diferencia absoluta entre el Node secundario y el principal.
1. Si el Node raíz es impar, devuelve » NO «.
2. Si el Node raíz es par, entonces los Nodes secundarios deben ser impares, por lo que la diferencia siempre debe ser impar. En el caso verdadero, devuelva » SÍ «, de lo contrario, devuelva » NO «.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new
// tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Utility function to recursively traverse tree and check the diff between child nodes
bool BSTUtil(Node * root){
if(root==NULL)
return true;
//if left nodes exist and absolute difference between left child and parent is divisible by 2, then return false
if(root->left!=NULL && abs(root->data - root->left->data)%2==0)
return false;
//if right nodes exist and absolute difference between right child and parent is divisible by 2, then return false
if(root->right!=NULL && abs(root->data - root->right->data)%2==0)
return false;
//recursively traverse left and right subtree
return BSTUtil(root->left) && BSTUtil(root->right);
}
// Utility function to check if binary tree is even-odd binary tree
bool isEvenOddBinaryTree(Node * root){
if(root==NULL)
return true;
// if root node is odd, return false
if(root->data%2 != 0)
return false;
return BSTUtil(root);
}
// driver program
int main()
{
// construct a tree
Node* root = newNode(5);
root->left = newNode(2);
root->right = newNode(6);
root->left->left = newNode(1);
root->left->right = newNode(5);
root->right->right = newNode(7);
root->left->right->left = newNode(12);
root->right->right->right = newNode(14);
root->right->right->left = newNode(16);
if(BSTUtil(root))
cout<<"YES";
else
cout<<"NO";
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// tree node
static class Node
{
public int data;
public Node left, right;
public Node(){
data = 0;
left = right = null;
}
}
// returns a new
// tree Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Utility function to recursively traverse tree and check the diff between child nodes
static boolean BSTUtil(Node root){
if(root == null)
return true;
//if left nodes exist and absolute difference between left child and parent is divisible by 2, then return false
if(root.left != null && Math.abs(root.data - root.left.data) % 2 == 0)
return false;
//if right nodes exist and absolute difference between right child and parent is divisible by 2, then return false
if(root.right != null && Math.abs(root.data - root.right.data) % 2 == 0)
return false;
//recursively traverse left and right subtree
return BSTUtil(root.left) && BSTUtil(root.right);
}
// Utility function to check if binary tree is even-odd binary tree
static boolean isEvenOddBinaryTree(Node root){
if(root == null)
return true;
// if root node is odd, return false
if(root.data%2 != 0)
return false;
return BSTUtil(root);
}
// Driver Code
public static void main(String args[])
{
// construct a tree
Node root = newNode(5);
root.left = newNode(2);
root.right = newNode(6);
root.left.left = newNode(1);
root.left.right = newNode(5);
root.right.right = newNode(7);
root.left.right.left = newNode(12);
root.right.right.right = newNode(14);
root.right.right.left = newNode(16);
if(BSTUtil(root))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by shinjanpatra
Python3
# tree node
class Node:
def __init__(self):
self.data = 0
self.left = self.right = None
# returns a new
# tree Node
def newNode(data):
temp = Node()
temp.data = data
temp.left = temp.right = None
return temp
# Utility function to recursively traverse tree
# and check the diff between child nodes
def BSTUtil(root):
if(root == None):
return True
# if left nodes exist and absolute difference between
# left child and parent is divisible by 2, then return False
if(root.left != None and abs(root.data - root.left.data) % 2 == 0):
return False
# if right nodes exist and absolute difference between
# right child and parent is divisible by 2, then return False
if(root.right != None and abs(root.data - root.right.data) % 2 == 0):
return False
# recursively traverse left and right subtree
return BSTUtil(root.left) and BSTUtil(root.right)
# Utility function to check if binary tree is even-odd binary tree
def isEvenOddBinaryTree(root):
if(root == None):
return True
# if root node is odd, return False
if(root.data%2 != 0):
return False
return BSTUtil(root)
# Driver Code
# construct a tree
root = newNode(5)
root.left = newNode(2)
root.right = newNode(6)
root.left.left = newNode(1)
root.left.right = newNode(5)
root.right.right = newNode(7)
root.left.right.left = newNode(12)
root.right.right.right = newNode(14)
root.right.right.left = newNode(16)
if(BSTUtil(root)):
print("YES")
else:
print("NO")
# This code is contributed by shinjanpatra
Javascript
<script>
// tree node
class Node{
constructor(){
this.data = 0
this.left = this.right = null
}
}
// returns a new
// tree Node
function newNode(data){
let temp = new Node()
temp.data = data
temp.left = temp.right = null
return temp
}
// Utility function to recursively traverse tree
// and check the diff between child nodes
function BSTUtil(root){
if(root == null)
return true
// if left nodes exist and absolute difference between
// left child and parent is divisible by 2, then return false
if(root.left != null && Math.abs(root.data - root.left.data) % 2 == 0)
return false
// if right nodes exist and absolute difference between
// right child and parent is divisible by 2, then return false
if(root.right != null && Math.abs(root.data - root.right.data) % 2 == 0)
return false
// recursively traverse left and right subtree
return BSTUtil(root.left) && BSTUtil(root.right)
}
// Utility function to check if binary tree is even-odd binary tree
function isEvenOddBinaryTree(root){
if(root == null)
return true
// if root node is odd, return false
if(root.data%2 != 0)
return false
return BSTUtil(root)
}
// Driver Code
// construct a tree
let root = newNode(5)
root.left = newNode(2)
root.right = newNode(6)
root.left.left = newNode(1)
root.left.right = newNode(5)
root.right.right = newNode(7)
root.left.right.left = newNode(12)
root.right.right.right = newNode(14)
root.right.right.left = newNode(16)
if(BSTUtil(root))
document.write("YES","</br>")
else
document.write("NO","</br>")
// This code is contributed by shinjanpatra
</script>
Producción
YES
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lavishgarg26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA