Dado un árbol binario , la tarea es encontrar el valor máximo de GCD desde cualquier ruta desde el Node raíz hasta el Node hoja .
Ejemplos:
Entrada: A continuación se muestra el árbol dado:
Salida: 3
Explicación:
Camino 1: 15->3->5 = mcd(15, 3, 15) =3
Camino 2: 15->3->1 =mcd(15, 3, 1) = 1
Camino 3: 15->7->31=mcd(15, 7, 31)= 1
Camino 4: 15->7->9 = mcd(15, 7, 9) =1, de estos 3 es el máximo.Entrada: A continuación se muestra el árbol dado:
Salida: 1
Enfoque: La idea es recorrer todos los caminos desde el Node raíz hasta el Node hoja y calcular el GCD de todos los Nodes que ocurrieron en ese camino. A continuación se muestran los pasos:
- Realice un recorrido de preorden en el árbol binario dado .
- Iterar sobre todas las rutas y realizar un seguimiento de todos los valores de ruta en una array.
- Siempre que encuentre un valor de hoja, busque el GCD de todos los valores en una array.
- Actualice el GCD al valor máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Initialise to update the maximum
// gcd value from all the path
int maxm = 0;
// Node structure
struct Node {
int val;
// Left & right child of the node
Node *left, *right;
// Initialize constructor
Node(int x)
{
val = x;
left = NULL;
right = NULL;
}
};
// Function to find gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// function to find the gcd of a path
int find_gcd(vector<int> arr)
{
if (arr.size() == 1)
return arr[0];
int g = arr[0];
for (int i = 1; i < arr.size(); i++) {
g = gcd(g, arr[i]);
}
return g;
}
// Function to find the maximum value
// of gcd from root to leaf
// in a Binary tree
void maxm_gcd(Node* root, vector<int> ans)
{
// Check if root is not null
if (!root)
return;
if (root->left == NULL
and root->right == NULL) {
ans.push_back(root->val);
// Find the maximum gcd of
// path value and store in
// global maxm variable
maxm = max(find_gcd(ans),
maxm);
return;
}
// Traverse left of binary tree
ans.push_back(root->val);
maxm_gcd(root->left, ans);
// Traverse right of the binary tree
maxm_gcd(root->right, ans);
}
// Driver Code
int main()
{
// Given Tree
Node* root = new Node(15);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(15);
root->left->right = new Node(1);
root->right->left = new Node(31);
root->right->right = new Node(9);
// Function Call
maxm_gcd(root, {});
// Print the maximum AND value
cout << maxm << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Initialise to update the maximum
// gcd value from all the path
static int maxm = 0;
// Node structure
static class Node
{
int val;
// Left & right child of the node
Node left, right;
// Initialize constructor
Node(int x)
{
val = x;
left = null;
right = null;
}
};
// Function to find gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the gcd of a path
static int find_gcd(Vector<Integer> arr)
{
if (arr.size() == 1)
return arr.get(0);
int g = arr.get(0);
for(int i = 1; i < arr.size(); i++)
{
g = gcd(g, arr.get(1));
}
return g;
}
// Function to find the maximum value
// of gcd from root to leaf
// in a Binary tree
static void maxm_gcd(Node root,
Vector<Integer> ans)
{
// Check if root is not null
if (root == null)
return;
if (root.left == null &&
root.right == null)
{
ans.add(root.val);
// Find the maximum gcd of
// path value and store in
// global maxm variable
maxm = Math.max(find_gcd(ans),
maxm);
return;
}
// Traverse left of binary tree
ans.add(root.val);
maxm_gcd(root.left, ans);
// Traverse right of the binary tree
maxm_gcd(root.right, ans);
}
// Driver Code
public static void main(String[] args)
{
// Given Tree
Node root = new Node(15);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(15);
root.left.right = new Node(1);
root.right.left = new Node(31);
root.right.right = new Node(9);
// Function call
maxm_gcd(root, new Vector<>());
// Print the maximum AND value
System.out.print(maxm + "\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of # the above approach # Initialise to update the maximum # gcd value from all the path global maxm maxm = 0 # Node structure class Node: # Initialize constructor def __init__(self, x): self.val = x self.left = None self.right = None # Function to find gcd of a and b def gcd(a, b): if(b == 0): return a return gcd(b, a % b) # Function to find the gcd of a path def find_gcd(arr): if(len(arr) == 1): return arr[0] g = arr[0] for i in range(1, len(arr)): g = gcd(g, arr[i]) return g # Function to find the maximum value # of gcd from root to leaf # in a Binary tree def maxm_gcd(root, ans): global maxm # Check if root is not null if(not root): return if(root.left == None and root.right == None): ans.append(root.val) # Find the maximum gcd of # path value and store in # global maxm variable maxm = max(find_gcd(ans), maxm) return # Traverse left of binary tree ans.append(root.val) maxm_gcd(root.left, ans) # Traverse right of the binary tree maxm_gcd(root.right, ans) # Driver Code if __name__ == '__main__': # Given Tree root = Node(15) root.left = Node(3) root.right = Node(7) root.left.left = Node(15) root.left.right = Node(1) root.right.left = Node(31) root.right.right = Node(9) # Function call maxm_gcd(root, []) # Print the maximum AND value print(maxm) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Initialise to update the maximum
// gcd value from all the path
static int maxm = 0;
// Node structure
class Node
{
public int val;
// Left & right child of the node
public Node left, right;
// Initialize constructor
public Node(int x)
{
val = x;
left = null;
right = null;
}
};
// Function to find gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the gcd of a path
static int find_gcd(List<int> arr)
{
if (arr.Count == 1)
return arr[0];
int g = arr[0];
for(int i = 1; i < arr.Count; i++)
{
g = gcd(g, arr[1]);
}
return g;
}
// Function to find the maximum value
// of gcd from root to leaf
// in a Binary tree
static void maxm_gcd(Node root,
List<int> ans)
{
// Check if root is not null
if (root == null)
return;
if (root.left == null &&
root.right == null)
{
ans.Add(root.val);
// Find the maximum gcd of
// path value and store in
// global maxm variable
maxm = Math.Max(find_gcd(ans),
maxm);
return;
}
// Traverse left of binary tree
ans.Add(root.val);
maxm_gcd(root.left, ans);
// Traverse right of the binary tree
maxm_gcd(root.right, ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given Tree
Node root = new Node(15);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(15);
root.left.right = new Node(1);
root.right.left = new Node(31);
root.right.right = new Node(9);
// Function call
maxm_gcd(root, new List<int>());
// Print the maximum AND value
Console.Write(maxm + "\n");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program for the above approach
// Initialise to update the maximum
// gcd value from all the path
let maxm = 0;
// Node structure
class Node
{
// Initialize constructor
constructor(x)
{
this.val = x;
this.left = null;
this.right = null;
}
}
var root;
// Function to find gcd of a and b
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the gcd of a path
function find_gcd(arr)
{
if (arr.length == 1)
return arr[0];
let g = arr[0];
for(let i = 1; i < arr.length; i++)
{
g = gcd(g, arr[1]);
}
return g;
}
// Function to find the maximum value
// of gcd from root to leaf
// in a Binary tree
function maxm_gcd(root, ans)
{
// Check if root is not null
if (root == null)
return;
if (root.left == null &&
root.right == null)
{
ans.push(root.val);
// Find the maximum gcd of
// path value and store in
// global maxm variable
maxm = Math.max(find_gcd(ans),
maxm);
return;
}
// Traverse left of binary tree
ans.push(root.val);
maxm_gcd(root.left, ans);
// Traverse right of the binary tree
maxm_gcd(root.right, ans);
}
// Driver Code
// Given Tree
root = new Node(15);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(15);
root.left.right = new Node(1);
root.right.left = new Node(31);
root.right.right = new Node(9);
// Function call
let arr = [];
maxm_gcd(root, arr);
// Print the maximum AND value
document.write(maxm);
// This code is contributed by Dharanendra L V.
</script>
Producción:
3
Complejidad del Tiempo : O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA