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>
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