XOR de ruta entre dos Nodes en un árbol binario

Posted on by Rudeus Greyrat

Dado un árbol binario con Nodes distintos y un par de dos Nodes. La tarea es encontrar el XOR de todos los Nodes que se encuentran en el camino entre los dos Nodes dados.
 

Por ejemplo , en el árbol binario anterior para los Nodes (3, 5), el XOR de la ruta será (3 XOR 1 XOR 0 XOR 2 XOR 5) = 5.
 

La idea es hacer uso de estas dos propiedades de XOR: 
 

  • XOR de los mismos elementos es cero.
  • XOR de un elemento con cero da el elemento mismo.

Ahora, para cada Node, busque y almacene el XOR a lo largo de la ruta desde la raíz hasta ese Node. Esto se puede hacer usando DFS simple . Ahora el XOR a lo largo de la ruta entre dos Nodes será: 
 

(XOR of path from root to first node) XOR (XOR of path from root to second node)

Explicación : Se presentan dos casos diferentes: 
 

  1. Si los dos Nodes están en diferentes subárboles de Nodes raíz. Ese es uno en el subárbol izquierdo y el otro en el subárbol derecho. En este caso, está claro que las fórmulas escritas anteriormente darán el resultado correcto ya que la ruta entre los Nodes pasa por la raíz con todos los Nodes distintos.
  2. Si los Nodes están en el mismo subárbol . Eso está en el subárbol izquierdo o en el subárbol derecho. En este caso, debe observar que la ruta desde la raíz hasta los dos Nodes tendrá un punto de intersección antes del cual la ruta es común para los dos Nodes desde la raíz. El XOR de esta ruta común se calcula dos veces y se cancela, por lo que no afecta el resultado.

Nota : para un solo par de Nodes, no es necesario almacenar la ruta desde las raíces hasta todos los Nodes. Esto es eficiente y está escrito considerando si hay una lista de pares de Nodes y para cada par tenemos que encontrar XOR de ruta entre los dos Nodes en un árbol binario.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find XOR of path between
// any two nodes in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
 
// structure of a node of binary tree
struct Node {
    int data;
    Node *left, *right;
};
 
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* getNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
 
// Function to store XOR of path from
// root to every node
// mp[x] will store XOR of path from root to node x
void storePath(Node* root, unordered_map<int, int>& mp, int XOR)
{
    // if root is NULL
    // there is no path
    if (!root)
        return;
 
    mp.insert(make_pair(root->data, XOR ^ root->data));
 
    XOR ^= root->data;
 
    if (root->left)
        storePath(root->left, mp, XOR);
 
    if (root->right)
        storePath(root->right, mp, XOR);
}
 
// Function to get XOR of nodes between any two nodes
int findXORPath(unordered_map<int, int> mp, int node1, int node2)
{
    return mp[node1] ^ mp[node2];
}
 
// Driver Code
int main()
{
    // binary tree formation
    struct Node* root = getNode(0);
    root->left = getNode(1);
    root->left->left = getNode(3);
    root->left->left->left = getNode(7);
    root->left->right = getNode(4);
    root->left->right->left = getNode(8);
    root->left->right->right = getNode(9);
    root->right = getNode(2);
    root->right->left = getNode(5);
    root->right->right = getNode(6);
 
    int XOR = 0;
    unordered_map<int, int> mp;
 
    int node1 = 3;
    int node2 = 5;
 
    // Store XOR path from root to every node
    storePath(root, mp, XOR);
 
    cout << findXORPath(mp, node1, node2);
 
    return 0;
}

Java

// Java program to find XOR of path between
// any two nodes in a Binary Tree
import java.util.*;
class Solution
{
 
// structure of a node of binary tree
static class Node {
    int data;
    Node left, right;
}
 
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
 static Node getNode(int data)
{
     Node newNode = new Node();
    newNode.data = data;
    newNode.left = newNode.right = null;
    return newNode;
}
 
// Function to store XOR of path from
// root to every node
// mp[x] will store XOR of path from root to node x
static void storePath(Node root, Map<Integer, Integer> mp, int XOR)
{
    // if root is null
    // there is no path
    if (root==null)
        return;
 
    mp.put(root.data, XOR ^ root.data);
 
    XOR ^= root.data;
 
    if (root.left!=null)
        storePath(root.left, mp, XOR);
 
    if (root.right!=null)
        storePath(root.right, mp, XOR);
}
 
// Function to get XOR of nodes between any two nodes
static int findXORPath(Map<Integer, Integer> mp, int node1, int node2)
{
    return mp.get(node1) ^ mp.get(node2);
}
 
// Driver Code
public static void main(String args[])
{
    // binary tree formation
     Node root = getNode(0);
    root.left = getNode(1);
    root.left.left = getNode(3);
    root.left.left.left = getNode(7);
    root.left.right = getNode(4);
    root.left.right.left = getNode(8);
    root.left.right.right = getNode(9);
    root.right = getNode(2);
    root.right.left = getNode(5);
    root.right.right = getNode(6);
 
    int XOR = 0;
    Map<Integer, Integer> mp= new HashMap<Integer, Integer>();
 
    int node1 = 3;
    int node2 = 5;
 
    // Store XOR path from root to every node
    storePath(root, mp, XOR);
 
    System.out.println( findXORPath(mp, node1, node2));
 
}
}
//contributed by Arnab Kundu

Python3

# Python3 program to find XOR of path between
# any two nodes in a Binary Tree
 
# Tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Helper function that allocates a node with the
# given data and None left and right pointers.
def getNode(data):
 
    newNode = Node(0)
    newNode.data = data
    newNode.left = newNode.right = None
    return newNode
 
mp = dict()
 
# Function to store XOR of path from
# root to every node
# mp[x] will store XOR of path from root to node x
def storePath( root, XOR) :
    global mp
     
    # if root is None
    # there is no path
    if (root == None) :
        return
 
    mp[root.data] = XOR ^ root.data;
 
    XOR = XOR ^ root.data
 
    if (root.left != None):
        storePath(root.left, XOR)
 
    if (root.right != None) :
        storePath(root.right, XOR)
 
# Function to get XOR of nodes between any two nodes
def findXORPath( node1, node2) :
    global mp
    return mp.get(node1,0) ^ mp.get(node2,0)
 
# Driver Code
 
# binary tree formation
root = getNode(0)
root.left = getNode(1)
root.left.left = getNode(3)
root.left.left.left = getNode(7)
root.left.right = getNode(4)
root.left.right.left = getNode(8)
root.left.right.right = getNode(9)
root.right = getNode(2)
root.right.left = getNode(5)
root.right.right = getNode(6)
 
XOR = 0
 
node1 = 3
node2 = 5
 
# Store XOR path from root to every node
storePath(root, XOR)
 
print( findXORPath( node1, node2))
 
# This code is contributed by Arnab Kundu

C#

// C# program to find XOR of path between
// any two nodes in a Binary Tree
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // structure of a node of binary tree
    class Node
    {
        public int data;
        public Node left, right;
    }
 
    /* Helper function that allocates
    a new node with the given data and
     null left and right pointers. */
    static Node getNode(int data)
    {
        Node newNode = new Node();
        newNode.data = data;
        newNode.left = newNode.right = null;
        return newNode;
    }
 
    // Function to store XOR of path from
    // root to every node
    // mp[x] will store XOR of path from root to node x
    static void storePath(Node root,
                Dictionary<int, int> mp, int XOR)
    {
        // if root is null
        // there is no path
        if (root == null)
            return;
 
        mp.Add(root.data, XOR ^ root.data);
 
        XOR ^= root.data;
 
        if (root.left != null)
            storePath(root.left, mp, XOR);
 
        if (root.right != null)
            storePath(root.right, mp, XOR);
    }
 
    // Function to get XOR of nodes between any two nodes
    static int findXORPath(Dictionary<int, int> mp,
                            int node1, int node2)
    {
        return mp[node1] ^ mp[node2];
    }
 
    // Driver Code
    public static void Main()
    {
        // binary tree formation
        Node root = getNode(0);
        root.left = getNode(1);
        root.left.left = getNode(3);
        root.left.left.left = getNode(7);
        root.left.right = getNode(4);
        root.left.right.left = getNode(8);
        root.left.right.right = getNode(9);
        root.right = getNode(2);
        root.right.left = getNode(5);
        root.right.right = getNode(6);
 
        int XOR = 0;
        Dictionary<int, int> mp = new Dictionary<int, int>();
 
        int node1 = 3;
        int node2 = 5;
 
        // Store XOR path from root to every node
        storePath(root, mp, XOR);
 
        Console.WriteLine( findXORPath(mp, node1, node2));
    }
}
 
/* This code is contributed PrinciRaj1992 */

Javascript

<script>
 
    // JavaScript program to find XOR of path between
    // any two nodes in a Binary Tree
     
    // structure of a node of binary tree
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
 
    /* Helper function that allocates a new node with the
    given data and null left and right pointers. */
    function getNode(data)
    {
        let newNode = new Node(data);
        return newNode;
    }
 
    // Function to store XOR of path from
    // root to every node
    // mp[x] will store XOR of path from root to node x
    function storePath(root, mp, XOR)
    {
        // if root is null
        // there is no path
        if (root==null)
            return;
 
        mp.set(root.data, XOR ^ root.data);
 
        XOR ^= root.data;
 
        if (root.left!=null)
            storePath(root.left, mp, XOR);
 
        if (root.right!=null)
            storePath(root.right, mp, XOR);
    }
 
    // Function to get XOR of nodes between any two nodes
    function findXORPath(mp, node1, node2)
    {
        return mp.get(node1) ^ mp.get(node2);
    }
     
    // binary tree formation
    let root = getNode(0);
    root.left = getNode(1);
    root.left.left = getNode(3);
    root.left.left.left = getNode(7);
    root.left.right = getNode(4);
    root.left.right.left = getNode(8);
    root.left.right.right = getNode(9);
    root.right = getNode(2);
    root.right.left = getNode(5);
    root.right.right = getNode(6);
   
    let XOR = 0;
    let mp= new Map();
   
    let node1 = 3;
    let node2 = 5;
   
    // Store XOR path from root to every node
    storePath(root, mp, XOR);
   
    document.write(findXORPath(mp, node1, node2));
 
</script>
Producción: 

5

 

Complejidad de Tiempo : O(N) 
Espacio Auxiliar : O(N), donde N es el número de Nodes.
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *