Valor máximo de Bitwise AND desde la raíz hasta la hoja en un árbol binario

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++ 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 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 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# 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

<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>

7

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)