Dado un árbol binario, escriba una función que devuelva verdadero si el árbol satisface la siguiente propiedad:
Para cada Node, el valor de los datos debe ser igual a la suma de los valores de los datos en los hijos izquierdo y derecho. Considere el valor de los datos como 0 para niños NULL.
Ejemplos:
Input :
10
/ \
8 2
/ \ \
3 5 2
Output : Yes
Input :
5
/ \
-2 7
/ \ \
1 6 7
Output : No
Ya hemos discutido el enfoque recursivo . En esta publicación se discute un enfoque iterativo.
Enfoque: La idea es usar una cola para hacer un recorrido de orden de nivel del árbol binario y verificar simultáneamente cada Node:
- Si el Node actual tiene dos hijos y si el Node actual es igual a la suma de sus hijos izquierdo y derecho.
- Si el Node actual acaba de dejar un hijo y si el Node actual es igual a su hijo izquierdo.
- Si el Node actual tiene el hijo derecho justo y si el Node actual es igual a su hijo derecho.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check children sum property
#include <bits/stdc++.h>
using namespace std;
// A binary tree node
struct Node {
int data;
Node *left, *right;
};
// Utility function to allocate memory for a new node
Node* newNode(int data)
{
Node* node = new (Node);
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Function to check if the tree holds
// children sum property
bool CheckChildrenSum(Node* root)
{
queue<Node*> q;
// Push the root node
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
// If the current node has both left and right children
if (temp->left && temp->right) {
// If the current node is not equal to
// the sum of its left and right children
// return false
if (temp->data != temp->left->data + temp->right->data)
return false;
q.push(temp->left);
q.push(temp->right);
}
// If the current node has right child
else if (!temp->left && temp->right) {
// If the current node is not equal to
// its right child return false
if (temp->data != temp->right->data)
return false;
q.push(temp->right);
}
// If the current node has left child
else if (!temp->right && temp->left) {
// If the current node is not equal to
// its left child return false
if (temp->data != temp->left->data)
return false;
q.push(temp->left);
}
}
// If the given tree has children
// sum property return true
return true;
}
// Driver code
int main()
{
Node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->right = newNode(2);
if (CheckChildrenSum(root))
printf("Yes");
else
printf("No");
return 0;
}
Java
// Java program to check children sum property
import java.util.*;
class GFG
{
// A binary tree node
static class Node
{
int data;
Node left, right;
}
// Utility function to allocate memory for a new node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Function to check if the tree holds
// children sum property
static boolean CheckChildrenSum(Node root)
{
Queue<Node> q = new LinkedList<Node>();
// add the root node
q.add(root);
while (q.size() > 0)
{
Node temp = q.peek();
q.remove();
// If the current node has both left and right children
if (temp.left != null && temp.right != null)
{
// If the current node is not equal to
// the sum of its left and right children
// return false
if (temp.data != temp.left.data + temp.right.data)
return false;
q.add(temp.left);
q.add(temp.right);
}
// If the current node has right child
else if (temp.left == null && temp.right != null)
{
// If the current node is not equal to
// its right child return false
if (temp.data != temp.right.data)
return false;
q.add(temp.right);
}
// If the current node has left child
else if (temp.right == null && temp.left != null)
{
// If the current node is not equal to
// its left child return false
if (temp.data != temp.left.data)
return false;
q.add(temp.left);
}
}
// If the given tree has children
// sum property return true
return true;
}
// Driver code
public static void main(String args[])
{
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(2);
if (CheckChildrenSum(root))
System.out.printf("Yes");
else
System.out.printf("No");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to check
# children sum property
# A binary tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to check if the tree holds
# children sum property
def CheckChildrenSum(root):
q = []
# Push the root node
q.append(root)
while len(q) != 0:
temp = q.pop()
# If the current node has both
# left and right children
if temp.left and temp.right:
# If the current node is not equal
# to the sum of its left and right
# children, return false
if (temp.data != temp.left.data +
temp.right.data):
return False
q.append(temp.left)
q.append(temp.right)
# If the current node has right child
elif not temp.left and temp.right:
# If the current node is not equal
# to its right child return false
if temp.data != temp.right.data:
return False
q.append(temp.right)
# If the current node has left child
elif not temp.right and temp.left:
# If the current node is not equal
# to its left child return false
if temp.data != temp.left.data:
return False
q.append(temp.left)
# If the given tree has children
# sum property return true
return True
# Driver code
if __name__ == "__main__":
root = Node(10)
root.left = Node(8)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(5)
root.right.right = Node(2)
if CheckChildrenSum(root):
print("Yes")
else:
print("No")
# This code is contributed
# by Rituraj Jain
C#
// C# program to check children sum property
using System;
using System.Collections.Generic;
class GFG
{
// A binary tree node
public class Node
{
public int data;
public Node left, right;
}
// Utility function to allocate
// memory for a new node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Function to check if the tree holds
// children sum property
static Boolean CheckChildrenSum(Node root)
{
Queue<Node> q = new Queue<Node>();
// add the root node
q.Enqueue(root);
while (q.Count > 0)
{
Node temp = q.Peek();
q.Dequeue();
// If the current node has both
// left and right children
if (temp.left != null &&
temp.right != null)
{
// If the current node is not equal to
// the sum of its left and right children
// return false
if (temp.data != temp.left.data +
temp.right.data)
return false;
q.Enqueue(temp.left);
q.Enqueue(temp.right);
}
// If the current node has right child
else if (temp.left == null &&
temp.right != null)
{
// If the current node is not equal to
// its right child return false
if (temp.data != temp.right.data)
return false;
q.Enqueue(temp.right);
}
// If the current node has left child
else if (temp.right == null &&
temp.left != null)
{
// If the current node is not equal to
// its left child return false
if (temp.data != temp.left.data)
return false;
q.Enqueue(temp.left);
}
}
// If the given tree has children
// sum property return true
return true;
}
// Driver code
public static void Main(String []args)
{
Node root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(2);
if (CheckChildrenSum(root))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to check children sum property
// A binary tree node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Utility function to allocate memory for a new node
function newNode(data)
{
let node = new Node(data);
return (node);
}
// Function to check if the tree holds
// children sum property
function CheckChildrenSum(root)
{
let q = [];
// add the root node
q.push(root);
while (q.length > 0)
{
let temp = q[0];
q.shift();
// If the current node has both left and right children
if (temp.left != null && temp.right != null)
{
// If the current node is not equal to
// the sum of its left and right children
// return false
if (temp.data != temp.left.data + temp.right.data)
return false;
q.push(temp.left);
q.push(temp.right);
}
// If the current node has right child
else if (temp.left == null && temp.right != null)
{
// If the current node is not equal to
// its right child return false
if (temp.data != temp.right.data)
return false;
q.push(temp.right);
}
// If the current node has left child
else if (temp.right == null && temp.left != null)
{
// If the current node is not equal to
// its left child return false
if (temp.data != temp.left.data)
return false;
q.push(temp.left);
}
}
// If the given tree has children
// sum property return true
return true;
}
let root = newNode(10);
root.left = newNode(8);
root.right = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(2);
if (CheckChildrenSum(root))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad temporal : O(N), donde N es el número total de Nodes en el árbol binario.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA