Se le da un árbol binario y una suma dada. La tarea es verificar si existe un subárbol cuya suma de todos los Nodes sea igual a la suma dada.
Examples :
// Para el árbol anterior
Entrada: suma = 17
Salida: «Sí»
// suma de todos los Nodes del subárbol {3, 5, 9} = 17
Entrada: suma = 11
Salida: «No»
// no existe ningún subárbol con la suma dada
La idea es atravesar el árbol en forma de Postorder porque aquí tenemos que pensar de abajo hacia arriba. Primero, calcule la suma del subárbol izquierdo, luego el subárbol derecho, y verifique si sum_left + sum_right + cur_node = sum cumple la condición que significa que existe cualquier subárbol con una suma dada. A continuación se muestra la implementación recursiva del algoritmo.
C++
// C++ program to find if there is a subtree with
// given sum
#include<bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
int data;
struct Node* left, *right;
};
/* utility that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newnode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// function to check if there exist any subtree with given sum
// cur_sum --> sum of current subtree from ptr as root
// sum_left --> sum of left subtree from ptr as root
// sum_right --> sum of right subtree from ptr as root
bool sumSubtreeUtil(struct Node *ptr, int *cur_sum, int sum)
{
// base condition
if (ptr == NULL)
{
*cur_sum = 0;
return false;
}
// Here first we go to left sub-tree, then right subtree
// then first we calculate sum of all nodes of subtree
// having ptr as root and assign it as cur_sum
// cur_sum = sum_left + sum_right + ptr->data
// after that we check if cur_sum == sum
int sum_left = 0, sum_right = 0;
return ( sumSubtreeUtil(ptr->left, &sum_left, sum) ||
sumSubtreeUtil(ptr->right, &sum_right, sum) ||
((*cur_sum = sum_left + sum_right + ptr->data) == sum));
}
// Wrapper over sumSubtreeUtil()
bool sumSubtree(struct Node *root, int sum)
{
// Initialize sum of subtree with root
int cur_sum = 0;
return sumSubtreeUtil(root, &cur_sum, sum);
}
// driver program to run the case
int main()
{
struct Node *root = newnode(8);
root->left = newnode(5);
root->right = newnode(4);
root->left->left = newnode(9);
root->left->right = newnode(7);
root->left->right->left = newnode(1);
root->left->right->right = newnode(12);
root->left->right->right->right = newnode(2);
root->right->right = newnode(11);
root->right->right->left = newnode(3);
int sum = 22;
if (sumSubtree(root, sum))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to find if there
// is a subtree with given sum
import java.util.*;
class GFG
{
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
static class Node
{
int data;
Node left, right;
}
static class INT
{
int v;
INT(int a)
{
v = a;
}
}
/* utility that allocates a new
node with the given data and
null left and right pointers. */
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// function to check if there exist
// any subtree with given sum
// cur_sum -. sum of current subtree
// from ptr as root
// sum_left -. sum of left subtree
// from ptr as root
// sum_right -. sum of right subtree
// from ptr as root
static boolean sumSubtreeUtil(Node ptr,
INT cur_sum,
int sum)
{
// base condition
if (ptr == null)
{
cur_sum = new INT(0);
return false;
}
// Here first we go to left
// sub-tree, then right subtree
// then first we calculate sum
// of all nodes of subtree having
// ptr as root and assign it as
// cur_sum. (cur_sum = sum_left +
// sum_right + ptr.data) after that
// we check if cur_sum == sum
INT sum_left = new INT(0),
sum_right = new INT(0);
return (sumSubtreeUtil(ptr.left, sum_left, sum) ||
sumSubtreeUtil(ptr.right, sum_right, sum) ||
((cur_sum.v = sum_left.v +
sum_right.v + ptr.data) == sum));
}
// Wrapper over sumSubtreeUtil()
static boolean sumSubtree(Node root, int sum)
{
// Initialize sum of
// subtree with root
INT cur_sum = new INT( 0);
return sumSubtreeUtil(root, cur_sum, sum);
}
// Driver Code
public static void main(String args[])
{
Node root = newnode(8);
root.left = newnode(5);
root.right = newnode(4);
root.left.left = newnode(9);
root.left.right = newnode(7);
root.left.right.left = newnode(1);
root.left.right.right = newnode(12);
root.left.right.right.right = newnode(2);
root.right.right = newnode(11);
root.right.right.left = newnode(3);
int sum = 22;
if (sumSubtree(root, sum))
System.out.println( "Yes");
else
System.out.println( "No");
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program to find if there is a
# subtree with given sum
# Binary Tree Node
""" utility that allocates a newNode
with the given key """
class newnode:
# Construct to create a newNode
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# function to check if there exist any
# subtree with given sum
# cur_sum -. sum of current subtree
# from ptr as root
# sum_left -. sum of left subtree from
# ptr as root
# sum_right -. sum of right subtree
# from ptr as root
def sumSubtreeUtil(ptr,cur_sum,sum):
# base condition
if (ptr == None):
cur_sum[0] = 0
return False
# Here first we go to left sub-tree,
# then right subtree then first we
# calculate sum of all nodes of subtree
# having ptr as root and assign it as cur_sum
# cur_sum = sum_left + sum_right + ptr.data
# after that we check if cur_sum == sum
sum_left, sum_right = [0], [0]
x=sumSubtreeUtil(ptr.left, sum_left, sum)
y=sumSubtreeUtil(ptr.right, sum_right, sum)
cur_sum[0] = (sum_left[0] +
sum_right[0] + ptr.data)
return ((x or y)or (cur_sum[0] == sum))
# Wrapper over sumSubtreeUtil()
def sumSubtree(root, sum):
# Initialize sum of subtree with root
cur_sum = [0]
return sumSubtreeUtil(root, cur_sum, sum)
# Driver Code
if __name__ == '__main__':
root = newnode(8)
root.left = newnode(5)
root.right = newnode(4)
root.left.left = newnode(9)
root.left.right = newnode(7)
root.left.right.left = newnode(1)
root.left.right.right = newnode(12)
root.left.right.right.right = newnode(2)
root.right.right = newnode(11)
root.right.right.left = newnode(3)
sum = 22
if (sumSubtree(root, sum)) :
print("Yes" )
else:
print("No")
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
using System;
// C# program to find if there
// is a subtree with given sum
public class GFG
{
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
public class Node
{
public int data;
public Node left, right;
}
public class INT
{
public int v;
public INT(int a)
{
v = a;
}
}
/* utility that allocates a new
node with the given data and
null left and right pointers. */
public static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// function to check if there exist
// any subtree with given sum
// cur_sum -. sum of current subtree
// from ptr as root
// sum_left -. sum of left subtree
// from ptr as root
// sum_right -. sum of right subtree
// from ptr as root
public static bool sumSubtreeUtil(Node ptr, INT cur_sum, int sum)
{
// base condition
if (ptr == null)
{
cur_sum = new INT(0);
return false;
}
// Here first we go to left
// sub-tree, then right subtree
// then first we calculate sum
// of all nodes of subtree having
// ptr as root and assign it as
// cur_sum. (cur_sum = sum_left +
// sum_right + ptr.data) after that
// we check if cur_sum == sum
INT sum_left = new INT(0), sum_right = new INT(0);
return (sumSubtreeUtil(ptr.left, sum_left, sum)
|| sumSubtreeUtil(ptr.right, sum_right, sum)
|| ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum));
}
// Wrapper over sumSubtreeUtil()
public static bool sumSubtree(Node root, int sum)
{
// Initialize sum of
// subtree with root
INT cur_sum = new INT(0);
return sumSubtreeUtil(root, cur_sum, sum);
}
// Driver Code
public static void Main(string[] args)
{
Node root = newnode(8);
root.left = newnode(5);
root.right = newnode(4);
root.left.left = newnode(9);
root.left.right = newnode(7);
root.left.right.left = newnode(1);
root.left.right.right = newnode(12);
root.left.right.right.right = newnode(2);
root.right.right = newnode(11);
root.right.right.left = newnode(3);
int sum = 22;
if (sumSubtree(root, sum))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript program to find if there
// is a subtree with given sum
/*
* A binary tree node has data, pointer to left child and a pointer to right
* child
*/
class Node {
constructor(){
this.data = 0;
this.left = null;
this.right = null;
}
}
class INT {
constructor(a) {
this.v = a;
}
}
/*
* utility that allocates a new node with the given data and null left and right
* pointers.
*/
function newnode(data) {
var node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// function to check if there exist
// any subtree with given sum
// cur_sum -. sum of current subtree
// from ptr as root
// sum_left -. sum of left subtree
// from ptr as root
// sum_right -. sum of right subtree
// from ptr as root
function sumSubtreeUtil( ptr, cur_sum , sum)
{
// base condition
if (ptr == null)
{
cur_sum = new INT(0);
return false;
}
// Here first we go to left
// sub-tree, then right subtree
// then first we calculate sum
// of all nodes of subtree having
// ptr as root and assign it as
// cur_sum. (cur_sum = sum_left +
// sum_right + ptr.data) after that
// we check if cur_sum == sum
var sum_left = new INT(0), sum_right = new INT(0);
return (sumSubtreeUtil(ptr.left, sum_left, sum) || sumSubtreeUtil(ptr.right, sum_right, sum)
|| ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum));
}
// Wrapper over sumSubtreeUtil()
function sumSubtree( root, sum)
{
// Initialize sum of
// subtree with root
var cur_sum = new INT(0);
return sumSubtreeUtil(root, cur_sum, sum);
}
// Driver Code
var root = newnode(8);
root.left = newnode(5);
root.right = newnode(4);
root.left.left = newnode(9);
root.left.right = newnode(7);
root.left.right.left = newnode(1);
root.left.right.right = newnode(12);
root.left.right.right.right = newnode(2);
root.right.right = newnode(11);
root.right.right.left = newnode(3);
var sum = 22;
if (sumSubtree(root, sum))
document.write("Yes");
else
document.write("No");
// This code is contributed by Rajput-Ji
</script>
Producción
Yes
Complejidad de tiempo: O (N), ya que estamos visitando cada Node una vez.
Espacio auxiliar: O(h), aquí h es la altura del árbol y el espacio adicional se usa debido a la pila de llamadas recursivas.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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