Dado un árbol binario , la tarea es encontrar el valor máximo de Bitwise AND desde cualquier ruta desde el Node raíz hasta el Node hoja .
Ejemplos:
Entrada: A continuación se muestra el gráfico dado:
Salida: 7
Explicación:
ruta 1: 15->3->5 = (15 & 3 & 5) = 1
ruta 2: 15->3->1 =(15 & 3 & 1) = 1
ruta 3: 15- >7->31=(15 & 7 & 31)= 7 (máximo)
camino 4: 15->7->9 = (15 & 7 & 9) =1, de estos 7 es el máximo.Entrada: A continuación se muestra el gráfico dado:
Salida: 6
Explicación:
Ruta 1: 31->3->7 = (31 & 3 & 7) = 3
Ruta 2: 31->3->1 = (31 & 3 & 1) = 1
Ruta 3: 31- >15->5 = (31 & 15 & 5) 5
Camino 4: 31->15->22 = (31 & 15 & 22) = 6, de estos 6 es el máximo.
Enfoque: La idea es recorrer todo el camino desde el Node raíz hasta el Node hoja y calcular el AND bit a bit de todos los Nodes que ocurrieron en ese camino. Mantenga una variable global para actualizar el valor AND bit a bit máximo de todas las rutas.
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
// AND 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 the maximum value
// of Bitwise AND from root to leaf
// in a Binary tree
void maxm_Anding(Node* root, int ans)
{
// Check if root is not null
if (!root)
return;
if (root->left == NULL
and root->right == NULL) {
ans &= root->val;
// Find the maximum AND value and
// store in global maxm variable
maxm = max(ans, maxm);
return;
}
// Traverse left of binary tree
maxm_Anding(root->left,
ans & root->val);
// Traverse right of the binary tree
maxm_Anding(root->right,
ans & root->val);
}
// 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(5);
root->left->right = new Node(1);
root->right->left = new Node(31);
root->right->right = new Node(9);
// Function Call
maxm_Anding(root, root->val);
// Print the maximum AND value
cout << maxm << endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
// Initialise to update the maximum
// AND 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 the maximum value
// of Bitwise AND from root to leaf
// in a Binary tree
static void maxm_Anding(Node root, int ans)
{
// Check if root is not null
if (root == null)
return;
if (root.left == null && root.right == null)
{
ans &= root.val;
// Find the maximum AND value and
// store in global maxm variable
maxm = Math.max(ans, maxm);
return;
}
// Traverse left of binary tree
maxm_Anding(root.left,
ans & root.val);
// Traverse right of the binary tree
maxm_Anding(root.right,
ans & root.val);
}
// 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(5);
root.left.right = new Node(1);
root.right.left = new Node(31);
root.right.right = new Node(9);
// Function Call
maxm_Anding(root, root.val);
// Print the maximum AND value
System.out.print(maxm + "\n");
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach # Initialise to update the maximum # AND value from all the path maxm = 0 # Node structure class Node: def __init__(self, x): self.val = x # Left & right child of the node self.left = None self.right = None # Function to find the maximum value # of Bitwise AND from root to leaf # in a Binary tree def maxm_Anding(root: Node, ans: int) -> None: global maxm # Check if root is not null if not root: return if (root.left is None and root.right is None): ans &= root.val # Find the maximum AND value and # store in global maxm variable maxm = max(ans, maxm) return # Traverse left of binary tree maxm_Anding(root.left, ans & root.val) # Traverse right of the binary tree maxm_Anding(root.right, ans & root.val) # Driver Code if __name__ == "__main__": # Given Tree root = Node(15) root.left = Node(3) root.right = Node(7) root.left.left = Node(5) root.left.right = Node(1) root.right.left = Node(31) root.right.right = Node(9) # Function Call maxm_Anding(root, root.val) # Print the maximum AND value print(maxm) # This code is contributed by sanjeev2552
C#
// C# program for the above approach
using System;
class GFG{
// Initialise to update the maximum
// AND 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 the maximum value
// of Bitwise AND from root to leaf
// in a Binary tree
static void maxm_Anding(Node root, int ans)
{
// Check if root is not null
if (root == null)
return;
if (root.left == null && root.right == null)
{
ans &= root.val;
// Find the maximum AND value and
// store in global maxm variable
maxm = Math.Max(ans, maxm);
return;
}
// Traverse left of binary tree
maxm_Anding(root.left,
ans & root.val);
// Traverse right of the binary tree
maxm_Anding(root.right,
ans & root.val);
}
// 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(5);
root.left.right = new Node(1);
root.right.left = new Node(31);
root.right.right = new Node(9);
// Function Call
maxm_Anding(root, root.val);
// Print the maximum AND value
Console.Write(maxm + "\n");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program for the above approach
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 the maximum value
// of Bitwise AND from root to leaf
// in a Binary tree
function maxm_Anding(root, ans)
{
// Check if root is not null
if (!root)
return;
if (root.left == null &&
root.right == null)
{
ans &= root.val;
// Find the maximum AND value and
// store in global maxm variable
maxm = Math.max(ans, maxm);
return;
}
// Traverse left of binary tree
maxm_Anding(root.left,
ans & root.val);
// Traverse right of the binary tree
maxm_Anding(root.right,
ans & root.val);
}
// Driver Code
root = new Node(15);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(5);
root.left.right = new Node(1);
root.right.left = new Node(31);
root.right.right = new Node(9);
// Function Call
maxm_Anding(root, root.val);
document.write(maxm);
// This code is contributed by Dharanendra L V.
</script>
Producción:
7
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
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