Dado un árbol binario y el valor de datos de un Node. La tarea es encontrar la suma de los Nodes primos del Node dado. Si el Node dado no tiene primos, devuelve -1.
Nota: se da que todos los Nodes tienen valores distintos y el Node dado existe en el árbol.
Ejemplos:
Input:
1
/ \
3 7
/ \ / \
6 5 4 13
/ / \
10 17 15
key = 13
Output: 11
Cousin nodes are 5 and 6 which gives sum 11.
Input:
1
/ \
3 7
/ \ / \
6 5 4 13
/ / \
10 17 15
key = 7
Output: -1
No cousin nodes of node having value 7.
Enfoque: El enfoque es hacer un recorrido de orden de nivel del árbol. Mientras realiza el recorrido del orden de niveles, busque la suma de los Nodes secundarios del siguiente nivel. Agregue el valor de un Node secundario a la suma y verifique si alguno de los Nodes secundarios es el Node de destino o no. En caso afirmativo, no agregue el valor de ninguno de los niños a la suma. Después de atravesar el nivel actual, si el Node de destino está presente en el siguiente nivel, finalice el recorrido del orden del nivel y la suma encontrada es la suma de los Nodes primos.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find sum of cousins
// of given node in binary tree.
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// A utility function to create a new
// Binary Tree Node
struct Node* newNode(int item)
{
struct Node* temp = new Node();
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// Function to find sum of cousins of
// a given node.
int findCousinSum(Node* root, int key)
{
if (root == NULL)
return -1;
// Root node has no cousins so return -1.
if (root->data == key) {
return -1;
}
// To store sum of cousins.
int currSum = 0;
// To store size of current level.
int size;
// To perform level order traversal.
queue<Node*> q;
q.push(root);
// To represent that target node is
// found.
bool found = false;
while (!q.empty()) {
// If target node is present at
// current level, then return
// sum of cousins stored in currSum.
if (found == true) {
return currSum;
}
// Find size of current level and
// traverse entire level.
size = q.size();
currSum = 0;
while (size) {
root = q.front();
q.pop();
// Check if either of the existing
// children of given node is target
// node or not. If yes then set
// found equal to true.
if ((root->left && root->left->data == key)
|| (root->right && root->right->data == key)) {
found = true;
}
// If target node is not children of
// current node, then its children can be cousin
// of target node, so add their value to sum.
else {
if (root->left) {
currSum += root->left->data;
q.push(root->left);
}
if (root->right) {
currSum += root->right->data;
q.push(root->right);
}
}
size--;
}
}
return -1;
}
// Driver Code
int main()
{
/*
1
/ \
3 7
/ \ / \
6 5 4 13
/ / \
10 17 15
*/
struct Node* root = newNode(1);
root->left = newNode(3);
root->right = newNode(7);
root->left->left = newNode(6);
root->left->right = newNode(5);
root->left->right->left = newNode(10);
root->right->left = newNode(4);
root->right->right = newNode(13);
root->right->left->left = newNode(17);
root->right->left->right = newNode(15);
cout << findCousinSum(root, 13) << "\n";
cout << findCousinSum(root, 7) << "\n";
return 0;
}
Java
// Java program to find sum of cousins
// of given node in binary tree.
import java.util.*;
class Sol
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
// A utility function to create a new
// Binary Tree Node
static Node newNode(int item)
{
Node temp = new Node();
temp.data = item;
temp.left = temp.right = null;
return temp;
}
// Function to find sum of cousins of
// a given node.
static int findCousinSum(Node root, int key)
{
if (root == null)
return -1;
// Root node has no cousins so return -1.
if (root.data == key)
{
return -1;
}
// To store sum of cousins.
int currSum = 0;
// To store size of current level.
int size;
// To perform level order traversal.
Queue<Node> q=new LinkedList<Node>();
q.add(root);
// To represent that target node is
// found.
boolean found = false;
while (q.size() > 0)
{
// If target node is present at
// current level, then return
// sum of cousins stored in currSum.
if (found == true)
{
return currSum;
}
// Find size of current level and
// traverse entire level.
size = q.size();
currSum = 0;
while (size > 0)
{
root = q.peek();
q.remove();
// Check if either of the existing
// children of given node is target
// node or not. If yes then set
// found equal to true.
if ((root.left!=null && root.left.data == key)
|| (root.right!=null && root.right.data == key))
{
found = true;
}
// If target node is not children of
// current node, then its children can be cousin
// of target node, so add their value to sum.
else
{
if (root.left != null)
{
currSum += root.left.data;
q.add(root.left);
}
if (root.right != null)
{
currSum += root.right.data;
q.add(root.right);
}
}
size--;
}
}
return -1;
}
// Driver Code
public static void main(String args[])
{
/*
1
/ \
3 7
/ \ / \
6 5 4 13
/ / \
10 17 15
*/
Node root = newNode(1);
root.left = newNode(3);
root.right = newNode(7);
root.left.left = newNode(6);
root.left.right = newNode(5);
root.left.right.left = newNode(10);
root.right.left = newNode(4);
root.right.right = newNode(13);
root.right.left.left = newNode(17);
root.right.left.right = newNode(15);
System.out.print( findCousinSum(root, 13) + "\n");
System.out.print( findCousinSum(root, 7) + "\n");
}
}
// This code is contributed by Arnab Kundu
Python3
""" Python3 program to find sum of cousins of given node in binary tree """ # A Binary Tree Node # Utility function to create a new tree node class newNode: # Constructor to create a newNode def __init__(self, data): self.data = data self.left = None self.right = None # Function to find sum of cousins of # a given node. def findCousinSum( root, key): if (root == None): return -1 # Root node has no cousins so return -1. if (root.data == key): return -1 # To store sum of cousins. currSum = 0 # To store size of current level. size = 0 # To perform level order traversal. q = [] q.append(root) # To represent that target node is # found. found = False while (len(q)): # If target node is present at # current level, then return # sum of cousins stored in currSum. if (found == True): return currSum # Find size of current level and # traverse entire level. size = len(q) currSum = 0 while (size): root = q[0] q.pop(0) # Check if either of the existing # children of given node is target # node or not. If yes then set # found equal to true. if ((root.left and root.left.data == key) or (root.right and root.right.data == key)) : found = True # If target node is not children of current # node, then its children can be cousin # of target node, so add their value to sum. else: if (root.left): currSum += root.left.data q.append(root.left) if (root.right) : currSum += root.right.data q.append(root.right) size -= 1 return -1 # Driver Code if __name__ == '__main__': """ 1 / \ 3 7 / \ / \ 6 5 4 13 / / \ 10 17 15 """ root = newNode(1) root.left = newNode(3) root.right = newNode(7) root.left.left = newNode(6) root.left.right = newNode(5) root.left.right.left = newNode(10) root.right.left = newNode(4) root.right.right = newNode(13) root.right.left.left = newNode(17) root.right.left.right = newNode(15) print(findCousinSum(root, 13)) print(findCousinSum(root, 7)) # This code is contributed by # SHUBHAMSINGH10
C#
// C# program to find sum of cousins
// of given node in binary tree.
using System;
using System.Collections.Generic;
class Sol
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
};
// A utility function to create a new
// Binary Tree Node
static Node newNode(int item)
{
Node temp = new Node();
temp.data = item;
temp.left = temp.right = null;
return temp;
}
// Function to find sum of cousins of
// a given node.
static int findCousinSum(Node root, int key)
{
if (root == null)
return -1;
// Root node has no cousins so return -1.
if (root.data == key)
{
return -1;
}
// To store sum of cousins.
int currSum = 0;
// To store size of current level.
int size;
// To perform level order traversal.
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
// To represent that target node is
// found.
bool found = false;
while (q.Count > 0)
{
// If target node is present at
// current level, then return
// sum of cousins stored in currSum.
if (found == true)
{
return currSum;
}
// Find size of current level and
// traverse entire level.
size = q.Count;
currSum = 0;
while (size > 0)
{
root = q.Peek();
q.Dequeue();
// Check if either of the existing
// children of given node is target
// node or not. If yes then set
// found equal to true.
if ((root.left != null && root.left.data == key)
|| (root.right != null && root.right.data == key))
{
found = true;
}
// If target node is not children of
// current node, then its children can be cousin
// of target node, so add their value to sum.
else
{
if (root.left != null)
{
currSum += root.left.data;
q.Enqueue(root.left);
}
if (root.right != null)
{
currSum += root.right.data;
q.Enqueue(root.right);
}
}
size--;
}
}
return -1;
}
// Driver Code
public static void Main(String []args)
{
/*
1
/ \
3 7
/ \ / \
6 5 4 13
/ / \
10 17 15
*/
Node root = newNode(1);
root.left = newNode(3);
root.right = newNode(7);
root.left.left = newNode(6);
root.left.right = newNode(5);
root.left.right.left = newNode(10);
root.right.left = newNode(4);
root.right.right = newNode(13);
root.right.left.left = newNode(17);
root.right.left.right = newNode(15);
Console.Write( findCousinSum(root, 13) + "\n");
Console.Write( findCousinSum(root, 7) + "\n");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to find sum of cousins
// of given node in binary tree.
// A Binary Tree Node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// A utility function to create a new
// Binary Tree Node
function newNode(item)
{
var temp = new Node();
temp.data = item;
temp.left = temp.right = null;
return temp;
}
// Function to find sum of cousins of
// a given node.
function findCousinSum(root, key)
{
if (root == null)
return -1;
// Root node has no cousins so return -1.
if (root.data == key)
{
return -1;
}
// To store sum of cousins.
var currSum = 0;
// To store size of current level.
var size;
// To perform level order traversal.
var q = [];
q.push(root);
// To represent that target node is
// found.
var found = false;
while (q.length > 0)
{
// If target node is present at
// current level, then return
// sum of cousins stored in currSum.
if (found == true)
{
return currSum;
}
// Find size of current level and
// traverse entire level.
size = q.length;
currSum = 0;
while (size > 0)
{
root = q[0];
q.shift();
// Check if either of the existing
// children of given node is target
// node or not. If yes then set
// found equal to true.
if ((root.left != null && root.left.data == key)
|| (root.right != null && root.right.data == key))
{
found = true;
}
// If target node is not children of
// current node, then its children can be cousin
// of target node, so add their value to sum.
else
{
if (root.left != null)
{
currSum += root.left.data;
q.push(root.left);
}
if (root.right != null)
{
currSum += root.right.data;
q.push(root.right);
}
}
size--;
}
}
return -1;
}
// Driver Code
/*
1
/ \
3 7
/ \ / \
6 5 4 13
/ / \
10 17 15
*/
var root = newNode(1);
root.left = newNode(3);
root.right = newNode(7);
root.left.left = newNode(6);
root.left.right = newNode(5);
root.left.right.left = newNode(10);
root.right.left = newNode(4);
root.right.right = newNode(13);
root.right.left.left = newNode(17);
root.right.left.right = newNode(15);
document.write( findCousinSum(root, 13) + "<br>");
document.write( findCousinSum(root, 7) + "<br>");
</script>
Producción:
11 -1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)