Dado un BST y un número. La tarea es verificar si el número dado es igual a la suma de todos los Nodes desde la hoja raíz a través de cualquiera de las rutas de la raíz a la hoja en el árbol de búsqueda binaria dado .
Enfoque : la idea es atravesar desde la raíz a todas las hojas de arriba hacia abajo manteniendo una array de ruta [] para almacenar la ruta actual de la raíz a la hoja. Durante el recorrido, almacene datos de todos los Nodes de la ruta actual en la array ruta []. Cada vez que se alcance un Node hoja, calcule la suma de todos los Nodes en la ruta actual usando la array ruta [] y verifique si es igual a la suma dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check if root to leaf path
// sum to a given number in BST
#include<bits/stdc++.h>
using namespace std;
// BST node
struct Node {
int data;
Node *left, *right;
};
/* Helper function that allocates a new node */
Node* newNode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Function to check if root to leaf path
// sum to a given number in BST
int checkThesum(struct Node *root, int path[], int i, int sum)
{
int sum1 = 0, x, y, j;
if(root == NULL)
return 0;
// insert the data of a node
path[i] = root->data;
// if the node is leaf
// add all the element in array
if(root->left==NULL&&root->right==NULL)
{
for(j = 0; j <= i; j++)
sum1 = sum1 + path[j];
// if the sum of root node to leaf
// node data is equal then return 1
if(sum == sum1)
return 1;
else
return 0;
}
x = checkThesum(root->left, path, i+1, sum);
// if x is 1, it means the given sum is matched
// with root to leaf node sum
if(x==1)
return 1;
else
{
return checkThesum(root->right, path, i+1, sum);
}
}
// Driver code
int main()
{
int path[100], sum = 164;
Node *root = newNode(45);
root->left = newNode(38);
root->left->left = newNode(33);
root->left->left->left = newNode(31);
root->left->left->right = newNode(35);
root->left->right = newNode(41);
root->left->right->left = newNode(40);
root->left->right->right = newNode(44);
root->right = newNode(50);
root->right->left = newNode(47);
root->right->left->left = newNode(46);
root->right->left->right = newNode(48);
root->right->right = newNode(52);
root->right->right->left = newNode(51);
root->right->right->right = newNode(55);
if(checkThesum(root, path, 0, sum)==1)
cout<<"YES\n";
else
cout<<"NO\n";
return 0;
}
Java
// Java program to check if
// root to leaf path sum to
// a given number in BST
class GFG
{
// BST node
static class Node
{
int data;
Node left, right;
}
/* Helper function that
allocates 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 root
// to leaf path sum to a
// given number in BST
static int checkThesum(Node root, int path[],
int i, int sum)
{
int sum1 = 0, x, y, j;
if(root == null)
return 0;
// insert the data of a node
path[i] = root.data;
// if the node is leaf
// add all the element in array
if(root.left == null &&
root.right == null)
{
for(j = 0; j <= i; j++)
sum1 = sum1 + path[j];
// if the sum of root node to leaf
// node data is equal then return 1
if(sum == sum1)
return 1;
else
return 0;
}
x = checkThesum(root.left, path,
i + 1, sum);
// if x is 1, it means the
// given sum is matched with
// root to leaf node sum
if(x == 1)
return 1;
else
{
return checkThesum(root.right, path,
i + 1, sum);
}
}
// Driver code
public static void main(String args[])
{
int path[] = new int[100], sum = 164;
Node root = newNode(45);
root.left = newNode(38);
root.left.left = newNode(33);
root.left.left.left = newNode(31);
root.left.left.right = newNode(35);
root.left.right = newNode(41);
root.left.right.left = newNode(40);
root.left.right.right = newNode(44);
root.right = newNode(50);
root.right.left = newNode(47);
root.right.left.left = newNode(46);
root.right.left.right = newNode(48);
root.right.right = newNode(52);
root.right.right.left = newNode(51);
root.right.right.right = newNode(55);
if(checkThesum(root, path, 0, sum) == 1)
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python program to check if root to leaf path
# sum to a given number in BST
import math
# BST node
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right= None
# Helper function that allocates a new node */
def newNode(data):
node = Node(data)
node.data = data
node.left = None
node.right = None
return node
# Function to check if root to leaf path
# sum to a given number in BST
def checkThesum(root, path, i, sum):
sum1 = 0
# x, y, j
if(root == None):
return 0
# insert the data of a node
path[i] = root.data
# if the node is leaf
# add all the element in array
if(root.left == None and root.right == None):
for j in range(0, i + 1):
sum1 = sum1 + path[j]
# if the sum of root node to leaf
# node data is equal then return 1
if(sum == sum1):
return 1
else:
return 0
x = checkThesum(root.left, path, i + 1, sum)
# if x is 1, it means the given sum is matched
# with root to leaf node sum
if(x == 1):
return 1
else:
return checkThesum(root.right, path, i + 1, sum)
# Driver code
if __name__=='__main__':
path = [None] * 100
sum = 164
root = newNode(45)
root.left = newNode(38)
root.left.left = newNode(33)
root.left.left.left = newNode(31)
root.left.left.right = newNode(35)
root.left.right = newNode(41)
root.left.right.left = newNode(40)
root.left.right.right = newNode(44)
root.right = newNode(50)
root.right.left = newNode(47)
root.right.left.left = newNode(46)
root.right.left.right = newNode(48)
root.right.right = newNode(52)
root.right.right.left = newNode(51)
root.right.right.right = newNode(55)
if(checkThesum(root, path, 0, sum) == 1):
print("YES")
else:
print("NO")
# This code is contributed by Srathore
C#
// C# program to check if
// root to leaf path sum to
// a given number in BST
using System;
class GFG
{
// BST node
public class Node
{
public int data;
public Node left, right;
}
/* Helper function that
allocates 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 root
// to leaf path sum to a
// given number in BST
static int checkThesum(Node root, int []path,
int i, int sum)
{
int sum1 = 0, x, y, j;
if(root == null)
return 0;
// insert the data of a node
path[i] = root.data;
// if the node is leaf
// add all the element in array
if(root.left == null &&
root.right == null)
{
for(j = 0; j <= i; j++)
sum1 = sum1 + path[j];
// if the sum of root node to leaf
// node data is equal then return 1
if(sum == sum1)
return 1;
else
return 0;
}
x = checkThesum(root.left, path,
i + 1, sum);
// if x is 1, it means the
// given sum is matched with
// root to leaf node sum
if(x == 1)
return 1;
else
{
return checkThesum(root.right, path,
i + 1, sum);
}
}
// Driver code
public static void Main(String []args)
{
int []path = new int[100];int sum = 164;
Node root = newNode(45);
root.left = newNode(38);
root.left.left = newNode(33);
root.left.left.left = newNode(31);
root.left.left.right = newNode(35);
root.left.right = newNode(41);
root.left.right.left = newNode(40);
root.left.right.right = newNode(44);
root.right = newNode(50);
root.right.left = newNode(47);
root.right.left.left = newNode(46);
root.right.left.right = newNode(48);
root.right.right = newNode(52);
root.right.right.left = newNode(51);
root.right.right.right = newNode(55);
if(checkThesum(root, path, 0, sum) == 1)
Console.Write("YES\n");
else
Console.Write("NO\n");
}
}
// This code is contributed 29AjayKumar
Javascript
<script>
// Javascript program to check if
// root to leaf path sum to
// a given number in BST
// BST node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
}
/* Helper function that
allocates a new node */
function newNode(data)
{
var node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Function to check if root
// to leaf path sum to a
// given number in BST
function checkThesum(root, path, i, sum)
{
var sum1 = 0, x, y, j;
if(root == null)
return 0;
// insert the data of a node
path[i] = root.data;
// if the node is leaf
// add all the element in array
if(root.left == null &&
root.right == null)
{
for(j = 0; j <= i; j++)
sum1 = sum1 + path[j];
// if the sum of root node to leaf
// node data is equal then return 1
if(sum == sum1)
return 1;
else
return 0;
}
x = checkThesum(root.left, path,
i + 1, sum);
// if x is 1, it means the
// given sum is matched with
// root to leaf node sum
if(x == 1)
return 1;
else
{
return checkThesum(root.right, path,
i + 1, sum);
}
}
// Driver code
var path = Array(100);
var sum = 164;
var root = newNode(45);
root.left = newNode(38);
root.left.left = newNode(33);
root.left.left.left = newNode(31);
root.left.left.right = newNode(35);
root.left.right = newNode(41);
root.left.right.left = newNode(40);
root.left.right.right = newNode(44);
root.right = newNode(50);
root.right.left = newNode(47);
root.right.left.left = newNode(46);
root.right.left.right = newNode(48);
root.right.right = newNode(52);
root.right.right.left = newNode(51);
root.right.right.right = newNode(55);
if(checkThesum(root, path, 0, sum) == 1)
document.write("YES<br>");
else
document.write("NO<br>");
// This code is contributed by itsok.
</script>
Producción:
YES
Publicación traducida automáticamente
Artículo escrito por Mohd_Saliem y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA