Dado un árbol binario , la tarea es encontrar el máximo de todos los valores XOR de todos los Nodes en la ruta desde la raíz hasta la hoja.
Ejemplos:
Input:
2
/ \
1 4
/ \
10 8
Output: 11
Explanation:
All the paths are:
2-1-10 XOR-VALUE = 9
2-1-8 XOR-VALUE = 11
2-4 XOR-VALUE = 6
Input:
2
/ \
1 4
/ \ / \
10 8 5 10
Output: 12
Acercarse:
- Para resolver la pregunta mencionada anteriormente, tenemos que recorrer el árbol de forma recursiva utilizando el recorrido de preorden. Para cada Node, siga calculando el XOR de la ruta desde la raíz hasta el Node actual.
XOR de la ruta del Node actual = (XOR de la ruta hasta el padre) ^ (valor del Node actual)
- Si el Node es un Node hoja que está a la izquierda y el hijo derecho de los Nodes actuales es NULL, entonces calculamos el max-Xor, como
max-Xor = max(max-Xor, cur-Xor).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to compute the
// Max-Xor value of path from
// the root to leaf of a Binary tree
#include <bits/stdc++.h>
using namespace std;
// Binary tree node
struct Node {
int data;
struct Node *left, *right;
};
// Function to create a new node
struct Node* newNode(int data)
{
struct Node* newNode = new Node;
newNode->data = data;
newNode->left
= newNode->right = NULL;
return (newNode);
}
// Function calculate the
// value of max-xor
void Solve(Node* root, int xr,
int& max_xor)
{
// Updating the xor value
// with the xor of the
// path from root to
// the node
xr = xr ^ root->data;
// Check if node is leaf node
if (root->left == NULL
&& root->right == NULL) {
max_xor = max(max_xor, xr);
return;
}
// Check if the left
// node exist in the tree
if (root->left != NULL) {
Solve(root->left, xr,
max_xor);
}
// Check if the right node
// exist in the tree
if (root->right != NULL) {
Solve(root->right, xr,
max_xor);
}
return;
}
// Function to find the
// required count
int findMaxXor(Node* root)
{
int xr = 0, max_xor = 0;
// Recursively traverse
// the tree and compute
// the max_xor
Solve(root, xr, max_xor);
// Return the result
return max_xor;
}
// Driver code
int main(void)
{
// Create the binary tree
struct Node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(4);
root->left->left = newNode(10);
root->left->right = newNode(8);
root->right->left = newNode(5);
root->right->right = newNode(10);
cout << findMaxXor(root);
return 0;
}
Java
// Java program to compute the
// Max-Xor value of path from
// the root to leaf of a Binary tree
class GFG {
// Binary tree node
static class Node {
int data = 0;
Node left = null, right = null;
};
// Function to create a new node
static Node newNode(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.left = newNode.right = null;
return (newNode);
}
// Function calculate the
// value of max-xor
static int Solve(Node root, int xr, int max_xor) {
// Updating the xor value
// with the xor of the
// path from root to
// the node
xr = xr ^ root.data;
// Check if node is leaf node
if (root.left == null
&& root.right == null) {
max_xor = Math.max(max_xor, xr);
return max_xor;
}
// Check if the left
// node exist in the tree
if (root.left != null) {
max_xor = Solve(root.left, xr,
max_xor);
}
// Check if the right node
// exist in the tree
if (root.right != null) {
max_xor = Solve(root.right, xr,
max_xor);
}
return max_xor;
}
// Function to find the
// required count
static int findMaxXor(Node root) {
int xr = 0, max_xor = 0;
// Recursively traverse
// the tree and compute
// the max_xor
max_xor = Solve(root, xr, max_xor);
// Return the result
return max_xor;
}
// Driver code
public static void main(String args[])
{
// Create the binary tree
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(4);
root.left.left = newNode(10);
root.left.right = newNode(8);
root.right.left = newNode(5);
root.right.right = newNode(10);
System.out.print(findMaxXor(root));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python3 program to compute the # Max-Xor value of path from # the root to leaf of a Binary tree # Binary tree node class Node: # Function to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Function calculate the # value of max-xor def Solve(root, xr, max_xor): # Updating the xor value # with the xor of the # path from root to # the node xr = xr ^ root.data # Check if node is leaf node if (root.left == None and root.right == None): max_xor[0] = max(max_xor[0], xr) # Check if the left # node exist in the tree if root.left != None: Solve(root.left, xr, max_xor) # Check if the right node # exist in the tree if root.right != None: Solve(root.right, xr, max_xor) return # Function to find the # required count def findMaxXor(root): xr, max_xor = 0, [0] # Recursively traverse # the tree and compute # the max_xor Solve(root, xr, max_xor) # Return the result return max_xor[0] # Driver code # Create the binary tree root = Node(2) root.left = Node(1) root.right = Node(4) root.left.left = Node(10) root.left.right = Node(8) root.right.left = Node(5) root.right.right = Node(10) print(findMaxXor(root)) # This code is contributed by Shivam Singh
Javascript
<script>
// JavaScript program to compute the
// Max-Xor value of path from
// the root to leaf of a Binary tree
// Binary tree node
class Node {
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Function to create a new node
function newNode(data)
{
var newNode = new Node;
newNode.data = data;
newNode.left
= newNode.right = null;
return (newNode);
}
// Function calculate the
// value of Math.max-xor
function Solve(root, xr, max_xor)
{
// Updating the xor value
// with the xor of the
// path from root to
// the node
xr = xr ^ root.data;
// Check if node is leaf node
if (root.left == null
&& root.right == null) {
max_xor = Math.max(max_xor, xr);
return max_xor;
}
// Check if the left
// node exist in the tree
if (root.left != null) {
max_xor = Solve(root.left, xr,
max_xor);
}
// Check if the right node
// exist in the tree
if (root.right != null) {
max_xor = Solve(root.right, xr,
max_xor);
}
return max_xor;
}
// Function to find the
// required count
function findMaxXor(root)
{
var xr = 0, max_xor = 0;
// Recursively traverse
// the tree and compute
// the max_xor
max_xor = Solve(root, xr, max_xor);
// Return the result
return max_xor;
}
// Driver code
// Create the binary tree
var root = newNode(2);
root.left = newNode(1);
root.right = newNode(4);
root.left.left = newNode(10);
root.left.right = newNode(8);
root.right.left = newNode(5);
root.right.right = newNode(10);
document.write( findMaxXor(root));
</script>
Producción:
12
Complejidad de tiempo: estamos iterando sobre cada Node solo una vez, por lo tanto, tomará un tiempo O (N) donde N es el número de Nodes en el árbol binario.
Complejidad del espacio auxiliar: la complejidad del espacio auxiliar será O(1) , ya que no se utiliza espacio adicional