Dado un árbol de búsqueda binario , un Node objetivo en el BST y un valor entero K , la tarea es encontrar la suma de todos los Nodes que están a una distancia K del Node objetivo cuyo valor es menor que el Node objetivo.
Ejemplos:
Entrada: objetivo = 7, K = 2
Salida: 11
Explicación:
Los Nodes a una distancia K(= 2) del Node 7 son 1, 4 y 6. Por lo tanto, la suma de los Nodes es 11.Entrada: objetivo = 5, K = 1
Salida: 4
Enfoque: El problema dado se puede resolver realizando DFS Traversal para K distancia por debajo del Node objetivo y realizar DFS Traversal hacia arriba K distancia desde el Node objetivo. Siga los pasos a continuación para resolver el problema:
- Defina una función kDistanceDownSum(root, k, &sum) y realice los siguientes pasos:
- Para el caso base , verifique si la raíz es nullptr y k es menor que 0 , luego regrese de la función .
- Si el valor de k es igual a 0 , agregue root->val a la variable sum y regrese.
- Llame a la misma función kDistanceDownSum(root->left, k-1, sum) y kDistanceDownSum(root->right, k – 1, sum) para los subárboles izquierdo y derecho.
- Para el caso base, verifique si la raíz es nullptr , luego devuelva -1 .
- Si la raíz es la misma que el objetivo , llame a la función kDistanceDownSum(root->left, k – 1, sum) para calcular la suma del primer tipo de Nodes y devuelva 0 (no es posible un segundo tipo de Nodes).
- Inicialice la variable dl como -1 y, si el objetivo es menor que root, establezca el valor de dl como el valor devuelto por la función kDistanceSum(root->left, target k, sum) .
- Si el valor de dl no es igual a -1 , entonces si la suma es igual a (dl + 1) , agregue el valor de root->data a la suma y luego devuelva -1 .
- De manera similar, inicialice la variable dr como -1 y si el destino es mayor que la raíz , actualice el valor de dr al valor devuelto por kDistanceSum(root->right, target k, sum) .
- Si el valor de dr no es igual a -1 , entonces si el valor de sum es igual a (dr + 1) , agregue el valor de root->data a sum . De lo contrario, llame a la función kDistanceDownSum(root->left, k – dr – 2, sum) y devuelva (1 + dr) .
- Después de realizar los pasos anteriores, imprima el valor de ans como la suma resultante.
La siguiente es la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Tree
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
// Constructor
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Function to add the node to the sum
// below the target node
void kDistanceDownSum(TreeNode* root,
int k, int& sum)
{
// Base Case
if (root == NULL || k < 0)
return;
// If Kth distant node is reached
if (k == 0) {
sum += root->data;
return;
}
// Recur for the left and the
// right subtrees
kDistanceDownSum(root->left,
k - 1, sum);
kDistanceDownSum(root->right,
k - 1, sum);
}
// Function to find the K distant nodes
// from target node, it returns -1 if
// target node is not present in tree
int kDistanceSum(TreeNode* root,
int target,
int k, int& sum)
{
// Base Case 1
if (root == NULL)
return -1;
// If target is same as root.
if (root->data == target) {
kDistanceDownSum(root->left,
k - 1, sum);
return 0;
}
// Recurr for the left subtree
int dl = -1;
// Tree is BST so reduce the
// search space
if (target < root->data) {
dl = kDistanceSum(root->left,
target, k, sum);
}
// Check if target node was found
// in left subtree
if (dl != -1) {
// If root is at distance k from
// the target
if (dl + 1 == k)
sum += root->data;
// Node less than target will be
// present in left
return -1;
}
// When node is not present in the
// left subtree
int dr = -1;
if (target > root->data) {
dr = kDistanceSum(root->right,
target, k, sum);
}
if (dr != -1) {
// If Kth distant node is reached
if (dr + 1 == k)
sum += root->data;
// Node less than target at k
// distance maybe present in the
// left tree
else
kDistanceDownSum(root->left,
k - dr - 2, sum);
return 1 + dr;
}
// If target was not present in the
// left nor in right subtree
return -1;
}
// Function to insert a node in BST
TreeNode* insertNode(int data,
TreeNode* root)
{
// If root is NULL
if (root == NULL) {
TreeNode* node = new TreeNode(data);
return node;
}
// Insert the data in right half
else if (data > root->data) {
root->right = insertNode(
data, root->right);
}
// Insert the data in left half
else if (data <= root->data) {
root->left = insertNode(
data, root->left);
}
// Return the root node
return root;
}
// Function to find the sum of K distant
// nodes from the target node having
// value less than target node
void findSum(TreeNode* root, int target,
int K)
{
// Stores the sum of nodes having
// values < target at K distance
int sum = 0;
kDistanceSum(root, target, K, sum);
// Print the resultant sum
cout << sum;
}
// Driver Code
int main()
{
TreeNode* root = NULL;
int N = 11;
int tree[] = { 3, 1, 7, 0, 2, 5,
10, 4, 6, 9, 8 };
// Create the Tree
for (int i = 0; i < N; i++) {
root = insertNode(tree[i], root);
}
int target = 7;
int K = 2;
findSum(root, target, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG{
static int sum;
// Structure of Tree
static class TreeNode {
int data;
TreeNode left;
TreeNode right;
// Constructor
TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to add the node to the sum
// below the target node
static void kDistanceDownSum(TreeNode root,
int k)
{
// Base Case
if (root == null || k < 0)
return;
// If Kth distant node is reached
if (k == 0) {
sum += root.data;
return;
}
// Recur for the left and the
// right subtrees
kDistanceDownSum(root.left,
k - 1);
kDistanceDownSum(root.right,
k - 1);
}
// Function to find the K distant nodes
// from target node, it returns -1 if
// target node is not present in tree
static int kDistanceSum(TreeNode root,
int target,
int k)
{
// Base Case 1
if (root == null)
return -1;
// If target is same as root.
if (root.data == target) {
kDistanceDownSum(root.left,
k - 1);
return 0;
}
// Recurr for the left subtree
int dl = -1;
// Tree is BST so reduce the
// search space
if (target < root.data) {
dl = kDistanceSum(root.left,
target, k);
}
// Check if target node was found
// in left subtree
if (dl != -1) {
// If root is at distance k from
// the target
if (dl + 1 == k)
sum += root.data;
// Node less than target will be
// present in left
return -1;
}
// When node is not present in the
// left subtree
int dr = -1;
if (target > root.data) {
dr = kDistanceSum(root.right,
target, k);
}
if (dr != -1) {
// If Kth distant node is reached
if (dr + 1 == k)
sum += root.data;
// Node less than target at k
// distance maybe present in the
// left tree
else
kDistanceDownSum(root.left,
k - dr - 2);
return 1 + dr;
}
// If target was not present in the
// left nor in right subtree
return -1;
}
// Function to insert a node in BST
static TreeNode insertNode(int data,
TreeNode root)
{
// If root is null
if (root == null) {
TreeNode node = new TreeNode(data);
return node;
}
// Insert the data in right half
else if (data > root.data) {
root.right = insertNode(
data, root.right);
}
// Insert the data in left half
else if (data <= root.data) {
root.left = insertNode(
data, root.left);
}
// Return the root node
return root;
}
// Function to find the sum of K distant
// nodes from the target node having
// value less than target node
static void findSum(TreeNode root, int target,
int K)
{
// Stores the sum of nodes having
// values < target at K distance
sum = 0;
kDistanceSum(root, target, K);
// Print the resultant sum
System.out.print(sum);
}
// Driver Code
public static void main(String[] args)
{
TreeNode root = null;
int N = 11;
int tree[] = { 3, 1, 7, 0, 2, 5,
10, 4, 6, 9, 8 };
// Create the Tree
for (int i = 0; i < N; i++) {
root = insertNode(tree[i], root);
}
int target = 7;
int K = 2;
findSum(root, target, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# python 3 program for the above approach # Structure of Tree sum = 0 class Node: # A constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Function to add the node to the sum # below the target node def kDistanceDownSum(root, k): global sum # Base Case if (root == None or k < 0): return # If Kth distant node is reached if (k == 0): sum += root.data return # Recur for the left and the # right subtrees kDistanceDownSum(root.left,k - 1) kDistanceDownSum(root.right,k - 1) # Function to find the K distant nodes # from target node, it returns -1 if # target node is not present in tree def kDistanceSum(root, target, k): global sum # Base Case 1 if (root == None): return -1 # If target is same as root. if (root.data == target): kDistanceDownSum(root.left,k - 1) return 0 # Recurr for the left subtree dl = -1 # Tree is BST so reduce the # search space if (target < root.data): dl = kDistanceSum(root.left, target, k) # Check if target node was found # in left subtree if (dl != -1): # If root is at distance k from # the target if (dl + 1 == k): sum += root.data # Node less than target will be # present in left return -1 # When node is not present in the # left subtree dr = -1 if (target > root.data): dr = kDistanceSum(root.right, target, k) if (dr != -1): # If Kth distant node is reached if (dr + 1 == k): sum += root.data # Node less than target at k # distance maybe present in the # left tree else: kDistanceDownSum(root.left, k - dr - 2) return 1 + dr # If target was not present in the # left nor in right subtree return -1 # Function to insert a node in BST def insertNode(data, root): # If root is NULL if (root == None): node = Node(data) return node # Insert the data in right half elif (data > root.data): root.right = insertNode(data, root.right) # Insert the data in left half elif(data <= root.data): root.left = insertNode(data, root.left) # Return the root node return root # Function to find the sum of K distant # nodes from the target node having # value less than target node def findSum(root, target, K): # Stores the sum of nodes having # values < target at K distance kDistanceSum(root, target, K) # Print the resultant sum print(sum) # Driver Code if __name__ == '__main__': root = None N = 11 tree = [3, 1, 7, 0, 2, 5,10, 4, 6, 9, 8] # Create the Tree for i in range(N): root = insertNode(tree[i], root) target = 7 K = 2 findSum(root, target, K) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
public class GFG{
static int sum;
// Structure of Tree
public
class TreeNode {
public
int data;
public
TreeNode left;
public
TreeNode right;
// Constructor
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to add the node to the sum
// below the target node
static void kDistanceDownSum(TreeNode root,
int k)
{
// Base Case
if (root == null || k < 0)
return;
// If Kth distant node is reached
if (k == 0) {
sum += root.data;
return;
}
// Recur for the left and the
// right subtrees
kDistanceDownSum(root.left,
k - 1);
kDistanceDownSum(root.right,
k - 1);
}
// Function to find the K distant nodes
// from target node, it returns -1 if
// target node is not present in tree
static int kDistanceSum(TreeNode root,
int target,
int k)
{
// Base Case 1
if (root == null)
return -1;
// If target is same as root.
if (root.data == target) {
kDistanceDownSum(root.left,
k - 1);
return 0;
}
// Recurr for the left subtree
int dl = -1;
// Tree is BST so reduce the
// search space
if (target < root.data) {
dl = kDistanceSum(root.left,
target, k);
}
// Check if target node was found
// in left subtree
if (dl != -1) {
// If root is at distance k from
// the target
if (dl + 1 == k)
sum += root.data;
// Node less than target will be
// present in left
return -1;
}
// When node is not present in the
// left subtree
int dr = -1;
if (target > root.data) {
dr = kDistanceSum(root.right,
target, k);
}
if (dr != -1) {
// If Kth distant node is reached
if (dr + 1 == k)
sum += root.data;
// Node less than target at k
// distance maybe present in the
// left tree
else
kDistanceDownSum(root.left,
k - dr - 2);
return 1 + dr;
}
// If target was not present in the
// left nor in right subtree
return -1;
}
// Function to insert a node in BST
static TreeNode insertNode(int data,
TreeNode root)
{
// If root is null
if (root == null) {
TreeNode node = new TreeNode(data);
return node;
}
// Insert the data in right half
else if (data > root.data) {
root.right = insertNode(
data, root.right);
}
// Insert the data in left half
else if (data <= root.data) {
root.left = insertNode(
data, root.left);
}
// Return the root node
return root;
}
// Function to find the sum of K distant
// nodes from the target node having
// value less than target node
static void findSum(TreeNode root, int target,
int K)
{
// Stores the sum of nodes having
// values < target at K distance
sum = 0;
kDistanceSum(root, target, K);
// Print the resultant sum
Console.Write(sum);
}
// Driver Code
public static void Main(String[] args)
{
TreeNode root = null;
int N = 11;
int []tree = { 3, 1, 7, 0, 2, 5,
10, 4, 6, 9, 8 };
// Create the Tree
for (int i = 0; i < N; i++) {
root = insertNode(tree[i], root);
}
int target = 7;
int K = 2;
findSum(root, target, K);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Structure of Tree
let sum = 0;
class TreeNode {
// Constructor
constructor(data = "", left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}
// Function to add the node to the sum
// below the target node
function kDistanceDownSum(root, k)
{
// Base Case
if (root == null || k < 0) {
return
}
// If Kth distant node is reached
if (k == 0) {
sum += root.data;
return;
}
// Recur for the left and the
// right subtrees
kDistanceDownSum(root.left, k - 1);
kDistanceDownSum(root.right, k - 1);
}
// Function to find the K distant nodes
// from target node, it returns -1 if
// target node is not present in tree
function kDistanceSum(root, target, k) {
// Base Case 1
if (root == null) return -1;
// If target is same as root.
if (root.data == target) {
kDistanceDownSum(root.left, k - 1);
return 0;
}
// Recurr for the left subtree
let dl = -1;
// Tree is BST so reduce the
// search space
if (target < root.data) {
dl = kDistanceSum(root.left, target, k);
}
// Check if target node was found
// in left subtree
if (dl != -1) {
// If root is at distance k from
// the target
if (dl + 1 == k) sum += root.data;
// Node less than target will be
// present in left
return -1;
}
// When node is not present in the
// left subtree
let dr = -1;
if (target > root.data) {
dr = kDistanceSum(root.right, target, k);
}
if (dr != -1) {
// If Kth distant node is reached
if (dr + 1 == k) sum += root.data;
// Node less than target at k
// distance maybe present in the
// left tree
else kDistanceDownSum(root.left, k - dr - 2);
return 1 + dr;
}
// If target was not present in the
// left nor in right subtree
return -1;
}
// Function to insert a node in BST
function insertNode(data, root) {
// If root is null
if (root == null) {
let node = new TreeNode(data);
return node;
}
// Insert the data in right half
else if (data > root.data) {
root.right = insertNode(data, root.right);
}
// Insert the data in left half
else if (data <= root.data) {
root.left = insertNode(data, root.left);
}
// Return the root node
return root;
}
// Function to find the sum of K distant
// nodes from the target node having
// value less than target node
function findSum(root, target, K) {
// Stores the sum of nodes having
// values < target at K distance
kDistanceSum(root, target, K, sum);
// Print the resultant sum
document.write(sum);
}
// Driver Code
let root = null;
let N = 11;
let tree = [3, 1, 7, 0, 2, 5, 10, 4, 6, 9, 8];
// Create the Tree
for (let i = 0; i < N; i++) {
root = insertNode(tree[i], root);
}
let target = 7;
let K = 2;
findSum(root, target, K);
</script>
Producción:
11
Complejidad Temporal:
Espacio Auxiliar: O(1)