Dado un árbol binario , la tarea es encontrar el Node cuyos hijos tienen el máximo producto de hermanos en el árbol binario dado. Si hay varios de estos Nodes, devuelva el Node que tenga el valor máximo.
Ejemplos:
Entrada: Árbol:
4
/ \
5 2
/ \
3 1
/ \
6 12
Salida: 3
Explicación: Para el árbol anterior, el producto máximo de los hermanos se forma para los Nodes 6 y 12, que son los hijos del Node 3.Entrada: Árbol:
1
/ \
3 5
/ \ / \
6 9 4 8
Salida: 3
Explicación: Para el árbol anterior, el producto máximo de los hermanos se forma para los Nodes 6 y 9, que son los hijos del Node 5.
Enfoque: para resolver este problema, se puede utilizar el recorrido de orden de nivel del árbol binario para encontrar la suma máxima de hermanos. Siga los siguientes pasos:
- Comience el recorrido del orden de nivel del árbol desde la raíz del árbol.
- Para cada Node, verifique si tiene ambos hijos.
- En caso afirmativo, encuentre el Node con el producto máximo de niños y almacene este valor de Node en una variable de referencia.
- Actualizar el valor del Node en la variable de referencia si se encuentra algún Node con mayor producto de hijos.
- Si el Node actual no tiene ambos hijos, omita ese Node
- Devuelve el valor del Node en la variable de referencia, ya que contiene el Node con el producto máximo de hijos o el padre de productos hermanos máximos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to find the Parent Node
// of maximum product Siblings
// in given Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Structure for Node
struct Node {
int data;
Node *left, *right;
};
// Function to get a new node
Node* getNode(int data)
{
// Allocate space
Node* newNode
= (Node*)malloc(sizeof(Node));
// Put in the data
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to get the parent
// of siblings with maximum product
int maxproduct(Node* root)
{
int mproduct = INT_MIN;
int ans = 0;
// Checking base case
if (root == NULL
|| (root->left == NULL
&& root->right == NULL))
return 0;
// Declaration of queue to run
// level order traversal
queue<Node*> q;
q.push(root);
// Loop to implement level order traversal
while (!q.empty()) {
Node* temp = q.front();
q.pop();
// If both the siblings are present
// then take their product
if (temp->right && temp->left) {
int curr_max
= temp->right->data
* temp->left->data;
if (mproduct < curr_max) {
mproduct = curr_max;
ans = temp->data;
}
else if (mproduct == curr_max) {
// if max product is equal to
// curr_max then consider node
// which has maximum value
ans = max(ans, temp->data);
}
}
// pushing childs in the queue
if (temp->right) {
q.push(temp->right);
}
if (temp->left) {
q.push(temp->left);
}
}
return ans;
}
// Driver Code
int main()
{
/* Binary tree creation
1
/ \
3 5
/ \ / \
6 9 4 8
*/
Node* root = getNode(1);
root->left = getNode(3);
root->right = getNode(5);
root->left->left = getNode(6);
root->left->right = getNode(9);
root->right->left = getNode(4);
root->right->right = getNode(8);
cout << maxproduct(root) << endl;
return 0;
}
Java
// Java code to find the Parent Node
// of maximum product Siblings
// in given Binary Tree
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// Structure for Node
static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to get a new node
public static Node getNode(int data) {
// Allocate space
Node newNode = new Node(data);
// Put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// Function to get the parent
// of siblings with maximum product
public static int maxproduct(Node root) {
int mproduct = Integer.MIN_VALUE;
int ans = 0;
// Checking base case
if (root == null
|| (root.left == null
&& root.right == null))
return 0;
// Declaration of queue to run
// level order traversal
Queue<Node> q = new LinkedList<Node>();
q.add(root);
// Loop to implement level order traversal
while (!q.isEmpty()) {
Node temp = q.peek();
q.remove();
// If both the siblings are present
// then take their product
if (temp.right != null && temp.left != null) {
int curr_max = temp.right.data
* temp.left.data;
if (mproduct < curr_max) {
mproduct = curr_max;
ans = temp.data;
} else if (mproduct == curr_max) {
// if max product is equal to
// curr_max then consider node
// which has maximum value
ans = Math.max(ans, temp.data);
}
}
// pushing childs in the queue
if (temp.right != null) {
q.add(temp.right);
}
if (temp.left != null) {
q.add(temp.left);
}
}
return ans;
}
// Driver Code
public static void main(String args[]) {
/*
* Binary tree creation
* 1
* / \
* 3 5
* / \ / \
* 6 9 4 8
*/
Node root = getNode(1);
root.left = getNode(3);
root.right = getNode(5);
root.left.left = getNode(6);
root.left.right = getNode(9);
root.right.left = getNode(4);
root.right.right = getNode(8);
System.out.println(maxproduct(root));
}
}
// This code is contributed by gfgking.
Python3
# Python Program to implement # the above approach # Structure of a node of binary tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to get a new node def getNode(data): # Allocate space newNode = Node(data) return newNode # Function to get the parent # of siblings with maximum product def maxproduct(root): mproduct = 10 ** -9 ans = 0; # Checking base case if (root == None or (root.left == None and root.right == None)): return 0; # Declaration of queue to run # level order traversal q = []; q.append(root); # Loop to implement level order traversal while (len(q)): temp = q[0]; q.pop(0); # If both the siblings are present # then take their product if (temp.right and temp.left): curr_max = temp.right.data * temp.left.data; if (mproduct < curr_max): mproduct = curr_max ans = temp.data elif (mproduct == curr_max): # if max product is equal to # curr_max then consider node # which has maximum value ans = max(ans, temp.data) # pushing childs in the queue if (temp.right): q.append(temp.right) if (temp.left): q.append(temp.left) return ans # Driver Code """ Binary tree creation 1 / \ 3 5 / \ / \ 6 9 4 8 """ root = getNode(1); root.left = getNode(3); root.right = getNode(5); root.left.left = getNode(6); root.left.right = getNode(9); root.right.left = getNode(4); root.right.right = getNode(8); print(maxproduct(root)); # This code is contributed by gfgking
C#
// C# code to find the Parent Node
// of maximum product Siblings
// in given Binary Tree
using System;
using System.Collections.Generic;
public class GFG {
// Structure for Node
class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to get a new node
static Node getNode(int data) {
// Allocate space
Node newNode = new Node(data);
// Put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// Function to get the parent
// of siblings with maximum product
static int maxproduct(Node root) {
int mproduct = int.MinValue;
int ans = 0;
// Checking base case
if (root == null
|| (root.left == null
&& root.right == null))
return 0;
// Declaration of queue to run
// level order traversal
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
// Loop to implement level order traversal
while (q.Count!=0) {
Node temp = q.Peek();
q.Dequeue();
// If both the siblings are present
// then take their product
if (temp.right != null && temp.left != null) {
int curr_max = temp.right.data
* temp.left.data;
if (mproduct < curr_max) {
mproduct = curr_max;
ans = temp.data;
} else if (mproduct == curr_max) {
// if max product is equal to
// curr_max then consider node
// which has maximum value
ans = Math.Max(ans, temp.data);
}
}
// pushing childs in the queue
if (temp.right != null) {
q.Enqueue(temp.right);
}
if (temp.left != null) {
q.Enqueue(temp.left);
}
}
return ans;
}
// Driver Code
public static void Main(String []args) {
/*
* Binary tree creation
* 1
* / \
* 3 5
* / \ / \
* 6 9 4 8
*/
Node root = getNode(1);
root.left = getNode(3);
root.right = getNode(5);
root.left.left = getNode(6);
root.left.right = getNode(9);
root.right.left = getNode(4);
root.right.right = getNode(8);
Console.WriteLine(maxproduct(root));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Structure of a node of binary tree
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to get a new node
function getNode(data)
{
// Allocate space
let newNode
= new Node(data);
return newNode;
}
// Function to get the parent
// of siblings with maximum product
function maxproduct(root) {
let mproduct = Number.MIN_VALUE;
let ans = 0;
// Checking base case
if (root == null
|| (root.left == null
&& root.right == null))
return 0;
// Declaration of queue to run
// level order traversal
let q = [];
q.push(root);
// Loop to implement level order traversal
while (!q.length == 0) {
let temp = q[0];
q.shift();
// If both the siblings are present
// then take their product
if (temp.right && temp.left) {
let curr_max
= temp.right.data
* temp.left.data;
if (mproduct < curr_max) {
mproduct = curr_max;
ans = temp.data;
}
else if (mproduct == curr_max) {
// if max product is equal to
// curr_max then consider node
// which has maximum value
ans = Math.max(ans, temp.data);
}
}
// pushing childs in the queue
if (temp.right) {
q.push(temp.right);
}
if (temp.left) {
q.push(temp.left);
}
}
return ans;
}
// Driver Code
/* Binary tree creation
1
/ \
3 5
/ \ / \
6 9 4 8
*/
let root = getNode(1);
root.left = getNode(3);
root.right = getNode(5);
root.left.left = getNode(6);
root.left.right = getNode(9);
root.right.left = getNode(4);
root.right.right = getNode(8);
document.write(maxproduct(root) + "<br>");
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(V) donde V es el número de Nodes del árbol.
Espacio Auxiliar: O(V).
Publicación traducida automáticamente
Artículo escrito por harshalkhond y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA