Dado un árbol binario y un número entero K , la tarea es comprobar si el árbol consta de un par de Nodes hoja con una suma exactamente K . En caso de múltiples pares, imprima cualquiera de ellos. De lo contrario, imprima -1.
Nota: Suponga que el árbol binario dado siempre tendrá más de 1 Node hoja.
Ejemplos:
Entrada: X = 13
1 / \ 2 3 / \ / \ 4 5 6 7 \ 8Salida: [5, 8]
Explicación:
El árbol binario dado consta de 4 Nodes hoja [4, 5, 6, 8].
El par de Nodes de valor 5 y 8 tienen suma 13.Entrada: X = 6
-1 / \ 2 3 / \ 4 5Salida: [-1]
Explicación:
El árbol binario dado consta de 3 Nodes hoja [4, 5, 3].
No existe un par válido de Nodes cuya suma de sus valores sea igual a 6.
Por lo tanto, imprima -1.
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar el árbol y almacenar todos los Nodes hoja en una array. Luego ordene la array y use la técnica de dos punteros para encontrar si existe o no un par requerido.
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando HashSet . Siga los pasos a continuación para resolver el problema:
- Cree un conjunto para almacenar valores de Nodes hoja.
- Atraviese el árbol y para cada Node de hoja, verifique si (K – valor del Node de hoja) existe en el conjunto desordenado o no.
- Si se encuentra que es verdadero, imprima el par de valores de Node.
- De lo contrario, almacene el valor del Node actual en el conjunto desordenado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores if a pair exists or not
bool pairFound = false;
// Struct binary tree node
struct Node {
int data;
Node *left, *right;
};
// Creates a new node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to check if a pair of leaf
// nodes exists with sum K
void pairSum(Node* root, int target,
unordered_set<int>& S)
{
// checks if root is NULL
if (!root)
return;
// Checks if the current node is a leaf node
if (!root->left and !root->right) {
// Checks for a valid pair of leaf nodes
if (S.count(target - root->data)) {
cout << target - root->data << " "
<< root->data;
pairFound = true;
return;
}
// Insert value of current node
// into the set
else
S.insert(root->data);
}
// Traverse left and right subtree
pairSum(root->left, target, S);
pairSum(root->right, target, S);
}
// Driver Code
int main()
{
// Construct binary tree
Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right = newNode(3);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->right->right = newNode(8);
// Stores the leaf nodes
unordered_set<int> S;
int K = 13;
pairSum(root, K, S);
if (pairFound == false)
cout << "-1";
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Stores if a pair exists or not
static boolean pairFound = false;
// Struct binary tree node
static class Node
{
int data;
Node left, right;
};
// Creates a new node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to check if a pair of leaf
// nodes exists with sum K
static void pairSum(Node root, int target,
HashSet<Integer> S)
{
// Checks if root is null
if (root == null)
return;
// Checks if the current node is a leaf node
if (root.left == null && root.right == null)
{
// Checks for a valid pair of leaf nodes
if (S.contains(target - root.data))
{
System.out.print(target - root.data +
" " + root.data);
pairFound = true;
return;
}
// Insert value of current node
// into the set
else
S.add(root.data);
}
// Traverse left and right subtree
pairSum(root.left, target, S);
pairSum(root.right, target, S);
}
// Driver Code
public static void main(String[] args)
{
// Construct binary tree
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right = newNode(3);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.right.right = newNode(8);
// Stores the leaf nodes
HashSet<Integer> S = new HashSet<Integer>();
int K = 13;
pairSum(root, K, S);
if (pairFound == false)
System.out.print("-1");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Stores if a pair exists or not pairFound = False S = set() # Struct binary tree node class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to check if a pair of # leaf nodes exists with sum K def pairSum(root, target): global pairFound global S # Checks if root is NULL if (root == None): return # Checks if the current node # is a leaf node if (root.left == None and root.right == None): temp = list(S) # Checks for a valid pair of leaf nodes if (temp.count(target - root.data)): print(target - root.data, root.data) pairFound = True return # Insert value of current node # into the set else: S.add(root.data) # Traverse left and right subtree pairSum(root.left, target) pairSum(root.right, target) # Driver Code if __name__ == '__main__': # Construct binary tree root = newNode(1) root.left = newNode(2) root.left.left = newNode(4) root.left.right = newNode(5) root.right = newNode(3) root.right.left = newNode(6) root.right.right = newNode(7) root.right.right.right = newNode(8) K = 13 pairSum(root, K) if (pairFound == False): print(-1) # This code is contributed by bgangwar59
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Stores if a pair exists or not
static bool pairFound = false;
// Struct binary tree node
class Node
{
public int data;
public Node left, right;
};
// Creates a new node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to check if a pair of leaf
// nodes exists with sum K
static void pairSum(Node root, int target,
HashSet<int> S)
{
// Checks if root is null
if (root == null)
return;
// Checks if the current node is a leaf node
if (root.left == null && root.right == null)
{
// Checks for a valid pair of leaf nodes
if (S.Contains(target - root.data))
{
Console.Write(target - root.data +
" " + root.data);
pairFound = true;
return;
}
// Insert value of current node
// into the set
else
S.Add(root.data);
}
// Traverse left and right subtree
pairSum(root.left, target, S);
pairSum(root.right, target, S);
}
// Driver Code
public static void Main(String[] args)
{
// Construct binary tree
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right = newNode(3);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.right.right = newNode(8);
// Stores the leaf nodes
HashSet<int> S = new HashSet<int>();
int K = 13;
pairSum(root, K, S);
if (pairFound == false)
Console.Write("-1");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the above approach
// Stores if a pair exists or not
let pairFound = false;
// Struct binary tree node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Creates a new node
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Function to check if a pair of leaf
// nodes exists with sum K
function pairSum(root, target, S)
{
// Checks if root is null
if (root == null)
return;
// Checks if the current node is a leaf node
if (root.left == null && root.right == null)
{
// Checks for a valid pair of leaf nodes
if (S.has(target - root.data))
{
document.write(target - root.data + " " +
root.data);
pairFound = true;
return;
}
// Insert value of current node
// into the set
else
S.add(root.data);
}
// Traverse left and right subtree
pairSum(root.left, target, S);
pairSum(root.right, target, S);
}
// Construct binary tree
let root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right = newNode(3);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.right.right = newNode(8);
// Stores the leaf nodes
let S = new Set();
let K = 13;
pairSum(root, K, S);
if (pairFound == false)
document.write("-1");
</script>
Producción:
5 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por chirags_30 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA