La suma de la ruta de la raíz a la hoja es igual a un número dado en BST

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *