Dado un árbol binario, encuentre si hay un par en la ruta de la raíz a una hoja tal que la suma de los valores en el par sea igual a los datos de la raíz. Por ejemplo, en el árbol a continuación no hay pares en ninguna ruta de raíz a hoja con una suma igual a los datos de la raíz.
La idea se basa en el hashing y el recorrido del árbol. La idea es similar al método 2 del problema de suma de pares de arreglos .
- Cree una tabla hash vacía.
- Comience a atravesar el árbol en forma de pedido anticipado.
- Si llegamos a un Node hoja, devolvemos falso.
- Para cada Node visitado, verifique si los datos de la raíz menos los datos del Node actual existen en la tabla hash o no. En caso afirmativo, devuelva verdadero. De lo contrario, inserte el Node actual en la tabla hash.
- Comprueba recursivamente los subárboles izquierdo y derecho.
- Elimine el Node actual de la tabla hash para que no aparezca en otras rutas de raíz a hoja.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find if there is a pair in any root
// to leaf path with sum equals to root's key.
#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 print root to leaf path which satisfies the condition
bool printPathUtil(Node *node, unordered_set<int> &s, int root_data)
{
// Base condition
if (node == NULL)
return false;
// Check if current node makes a pair with any of the
// existing elements in set.
int rem = root_data - node->data;
if (s.find(rem) != s.end())
return true;
// Insert current node in set
s.insert(node->data);
// If result returned by either left or right child is
// true, return true.
bool res = printPathUtil(node->left, s, root_data) ||
printPathUtil(node->right, s, root_data);
// Remove current node from hash table
s.erase(node->data);
return res;
}
// A wrapper over printPathUtil()
bool isPathSum(Node *root)
{
// create an empty hash table
unordered_set<int> s;
// Recursively check in left and right subtrees.
return printPathUtil(root->left, s, root->data) ||
printPathUtil(root->right, s, root->data);
}
// 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);
isPathSum(root)? cout << "Yes" : cout << "No";
return 0;
}
Java
// Java program to find if there is a pair in any root
// to leaf path with sum equals to root's key.
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;
};
/* 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 print root to leaf path which satisfies the condition
static boolean printPathUtil(Node node, HashSet<Integer> s, int root_data)
{
// Base condition
if (node == null)
return false;
// Check if current node makes a pair with any of the
// existing elements in set.
int rem = root_data - node.data;
if (s.contains(rem))
return true;
// Insert current node in set
s.add(node.data);
// If result returned by either left or right child is
// true, return true.
boolean res = printPathUtil(node.left, s, root_data) ||
printPathUtil(node.right, s, root_data);
// Remove current node from hash table
s.remove(node.data);
return res;
}
// A wrapper over printPathUtil()
static boolean isPathSum(Node root)
{
// create an empty hash table
HashSet<Integer> s = new HashSet<Integer>();
// Recursively check in left and right subtrees.
return printPathUtil(root.left, s, root.data) ||
printPathUtil(root.right, s, root.data);
}
// 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);
System.out.print(isPathSum(root)==true ?"Yes" : "No");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find if there is a
# pair in any root to leaf path with sum
# equals to root's key
# A binary tree node has data, pointer to
# left child and a pointer to right child
""" utility that allocates a new node with the
given data and None left and right pointers. """
class newnode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Function to print root to leaf path which
# satisfies the condition
def printPathUtil(node, s, root_data) :
# Base condition
if (node == None) :
return False
# Check if current node makes a pair
# with any of the existing elements in set.
rem = root_data - node.data
if rem in s:
return True
# Insert current node in set
s.add(node.data)
# If result returned by either left or
# right child is True, return True.
res = printPathUtil(node.left, s, root_data) or \
printPathUtil(node.right, s, root_data)
# Remove current node from hash table
s.remove(node.data)
return res
# A wrapper over printPathUtil()
def isPathSum(root) :
# create an empty hash table
s = set()
# Recursively check in left and right subtrees.
return printPathUtil(root.left, s, root.data) or \
printPathUtil(root.right, s, root.data)
# 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)
print("Yes") if (isPathSum(root)) else print("No")
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to find if there is a pair in any root
// to leaf path with sum equals to root's key.
using System;
using System.Collections.Generic;
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;
};
/* 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 print root to leaf path
// which satisfies the condition
static bool printPathUtil(Node node,
HashSet<int> s,
int root_data)
{
// Base condition
if (node == null)
return false;
// Check if current node makes a pair
// with any of the existing elements in set.
int rem = root_data - node.data;
if (s.Contains(rem))
return true;
// Insert current node in set
s.Add(node.data);
// If result returned by either left or
// right child is true, return true.
bool res = printPathUtil(node.left, s, root_data) ||
printPathUtil(node.right, s, root_data);
// Remove current node from hash table
s.Remove(node.data);
return res;
}
// A wrapper over printPathUtil()
static bool isPathSum(Node root)
{
// create an empty hash table
HashSet<int> s = new HashSet<int>();
// Recursively check in left and right subtrees.
return printPathUtil(root.left, s, root.data) ||
printPathUtil(root.right, s, root.data);
}
// 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);
Console.Write(isPathSum(root) == true ?
"Yes" : "No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find if there is a pair in any root
// to leaf path with sum equals to root's key.
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
/* utility that allocates a new node with the
given data and null left and right pointers. */
constructor(data)
{
this.data=data;
this.left=this.right=null;
}
}
// Function to print root to leaf path which satisfies the condition
function printPathUtil(node,s,root_data)
{
// Base condition
if (node == null)
return false;
// Check if current node makes a pair with any of the
// existing elements in set.
let rem = root_data - node.data;
if (s.has(rem))
return true;
// Insert current node in set
s.add(node.data);
// If result returned by either left or right child is
// true, return true.
let res = printPathUtil(node.left, s, root_data) ||
printPathUtil(node.right, s, root_data);
// Remove current node from hash table
s.delete(node.data);
return res;
}
// A wrapper over printPathUtil()
function isPathSum(root)
{
// create an empty hash table
let s = new Set();
// Recursively check in left and right subtrees.
return printPathUtil(root.left, s, root.data) ||
printPathUtil(root.right, s, root.data);
}
// Driver code
let root = new Node(8);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(9);
root.left.right = new Node(7);
root.left.right.left = new Node(1);
root.left.right.right = new Node(12);
root.left.right.right.right = new Node(2);
root.right.right = new Node(11);
root.right.right.left = new Node(3);
document.write(isPathSum(root)==true ?"Yes" : "No");
// This code is contributed by rag2127
</script>
Producción
Yes
Complejidad de tiempo: O(n) bajo el supuesto de que la búsqueda hash, la inserción y el borrado toman el tiempo O(1).
Ejercicio: Extienda la solución anterior para imprimir todas las rutas de la raíz a la hoja que tienen un par con suma igual a los datos de la raíz.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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.
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