Dado un árbol binario , la tarea es imprimir todas las rutas de la raíz a la hoja de este árbol cuyo valor xor no sea cero.
Ejemplos:
Input:
10
/ \
10 3
/ \
10 3
/ \ / \
7 3 42 13
/
7
Output:
10 3 10 7
10 3 3 42
Explanation:
All the paths in the given binary tree are :
{10, 10} xor value of the path is
= 10 ^ 10 = 0
{10, 3, 10, 7} xor value of the path is
= 10 ^ 3 ^ 10 ^ 7 != 0
{10, 3, 3, 42} xor value of the path is
= 10 ^ 3 ^ 3 ^ 42 != 0
{10, 3, 10, 3} xor value of the path is
= 10 ^ 3 ^ 10 ^ 3 = 0
{10, 3, 3, 13, 7} xor value of the path is
= 10 ^ 3 ^ 3 ^ 13 ^ 7 = 0.
Hence, {10, 3, 10, 7} and {10, 3, 3, 42} are
the paths whose xor value is non-zero.
Input:
5
/ \
21 77
/ \ \
5 21 16
\ /
5 3
Output :
5 21 5
5 77 16 3
Explanation:
{5, 21, 5} and {5, 77, 16, 3} are the paths
whose xor value is non-zero.
Enfoque:
Para resolver el problema mencionado anteriormente, la idea principal es atravesar el árbol y verificar si el xor de todos los elementos en ese camino es cero o no.
- Necesitamos atravesar el árbol recursivamente usando Pre-Order Traversal .
- Para cada Node, siga calculando el XOR de la ruta desde la raíz hasta el Node actual.
- Si el Node es un Node de hoja que está a la izquierda y el hijo derecho de los Nodes actuales es NULL, entonces verificamos si el valor xor de la ruta es distinto de cero o no, si es así, imprimimos la ruta completa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Print all the Paths of a
// Binary Tree whose XOR gives a non-zero value
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function to check whether Path
// is has non-zero xor value or not
bool PathXor(vector<int>& path)
{
int ans = 0;
// Iterating through the array
// to find the xor value
for (auto x : path) {
ans ^= x;
}
return (ans != 0);
}
// Function to print a path
void printPaths(vector<int>& path)
{
for (auto x : path) {
cout << x << " ";
}
cout << endl;
}
// Function to find the paths of
// binary tree having non-zero xor value
void findPaths(struct Node* root,
vector<int>& path)
{
// Base case
if (root == NULL)
return;
// Store the value in path vector
path.push_back(root->key);
// Recursively call for left sub tree
findPaths(root->left, path);
// Recursively call for right sub tree
findPaths(root->right, path);
// Condition to check, if leaf node
if (root->left == NULL
&& root->right == NULL) {
// Condition to check,
// if path has non-zero xor or not
if (PathXor(path)) {
// Print the path
printPaths(path);
}
}
// Remove the last element
// from the path vector
path.pop_back();
}
// Function to find the paths
// having non-zero xor value
void printPaths(struct Node* node)
{
vector<int> path;
findPaths(node, path);
}
// Driver Code
int main()
{
/* 10
/ \
10 3
/ \
10 3
/ \ / \
7 3 42 13
/
7
*/
// Create Binary Tree as shown
Node* root = newNode(10);
root->left = newNode(10);
root->right = newNode(3);
root->right->left = newNode(10);
root->right->right = newNode(3);
root->right->left->left = newNode(7);
root->right->left->right = newNode(3);
root->right->right->left = newNode(42);
root->right->right->right = newNode(13);
root->right->right->right->left = newNode(7);
// Print non-zero XOR Paths
printPaths(root);
return 0;
}
Java
// Java program to Print all the Paths of a
// Binary Tree whose XOR gives a non-zero value
import java.util.*;
class GFG{
// A Tree node
static class Node
{
int key;
Node left, right;
};
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to check whether Path
// is has non-zero xor value or not
static boolean PathXor(Vector<Integer> path)
{
int ans = 0;
// Iterating through the array
// to find the xor value
for (int x : path)
{
ans ^= x;
}
return (ans != 0);
}
// Function to print a path
static void printPaths(Vector<Integer> path)
{
for (int x : path)
{
System.out.print(x + " ");
}
System.out.println();
}
// Function to find the paths of
// binary tree having non-zero xor value
static void findPaths(Node root,
Vector<Integer> path)
{
// Base case
if (root == null)
return;
// Store the value in path vector
path.add(root.key);
// Recursively call for left sub tree
findPaths(root.left, path);
// Recursively call for right sub tree
findPaths(root.right, path);
// Condition to check, if leaf node
if (root.left == null &&
root.right == null)
{
// Condition to check,
// if path has non-zero xor or not
if (PathXor(path))
{
// Print the path
printPaths(path);
}
}
// Remove the last element
// from the path vector
path.remove(path.size() - 1);
}
// Function to find the paths
// having non-zero xor value
static void printPaths(Node node)
{
Vector<Integer> path = new Vector<Integer>();
findPaths(node, path);
}
// Driver Code
public static void main(String[] args)
{
/* 10
/ \
10 3
/ \
10 3
/ \ / \
7 3 42 13
/
7
*/
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(10);
root.right = newNode(3);
root.right.left = newNode(10);
root.right.right = newNode(3);
root.right.left.left = newNode(7);
root.right.left.right = newNode(3);
root.right.right.left = newNode(42);
root.right.right.right = newNode(13);
root.right.right.right.left = newNode(7);
// Print non-zero XOR Paths
printPaths(root);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to print all # the paths of a Binary Tree # whose XOR gives a non-zero value # A Tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to check whether Path # is has non-zero xor value or not def PathXor(path: list) -> bool: ans = 0 # Iterating through the array # to find the xor value for x in path: ans ^= x return (ans != 0) # Function to print a path def printPathsList(path: list) -> None: for x in path: print(x, end = " ") print() # Function to find the paths of # binary tree having non-zero xor value def findPaths(root: Node, path: list) -> None: # Base case if (root == None): return # Store the value in path vector path.append(root.key) # Recursively call for left sub tree findPaths(root.left, path) # Recursively call for right sub tree findPaths(root.right, path) # Condition to check, if leaf node if (root.left == None and root.right == None): # Condition to check, if path # has non-zero xor or not if (PathXor(path)): # Print the path printPathsList(path) # Remove the last element # from the path vector path.pop() # Function to find the paths # having non-zero xor value def printPaths(node: Node) -> None: path = [] newNode = node findPaths(newNode, path) # Driver Code if __name__ == "__main__": ''' 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 ''' # Create Binary Tree as shown root = Node(10) root.left = Node(10) root.right = Node(3) root.right.left = Node(10) root.right.right = Node(3) root.right.left.left = Node(7) root.right.left.right = Node(3) root.right.right.left = Node(42) root.right.right.right = Node(13) root.right.right.right.left = Node(7) # Print non-zero XOR Paths printPaths(root) # This code is contributed by sanjeev2552
C#
// C# program to Print all the Paths of a
// Binary Tree whose XOR gives a non-zero value
using System;
using System.Collections.Generic;
class GFG{
// A Tree node
class Node
{
public int key;
public Node left, right;
};
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to check whether Path
// is has non-zero xor value or not
static bool PathXor(List<int> path)
{
int ans = 0;
// Iterating through the array
// to find the xor value
foreach (int x in path)
{
ans ^= x;
}
return (ans != 0);
}
// Function to print a path
static void printPaths(List<int> path)
{
foreach (int x in path)
{
Console.Write(x + " ");
}
Console.WriteLine();
}
// Function to find the paths of
// binary tree having non-zero xor value
static void findPaths(Node root,
List<int> path)
{
// Base case
if (root == null)
return;
// Store the value in path vector
path.Add(root.key);
// Recursively call for left sub tree
findPaths(root.left, path);
// Recursively call for right sub tree
findPaths(root.right, path);
// Condition to check, if leaf node
if (root.left == null &&
root.right == null)
{
// Condition to check,
// if path has non-zero xor or not
if (PathXor(path))
{
// Print the path
printPaths(path);
}
}
// Remove the last element
// from the path vector
path.RemoveAt(path.Count - 1);
}
// Function to find the paths
// having non-zero xor value
static void printPaths(Node node)
{
List<int> path = new List<int>();
findPaths(node, path);
}
// Driver Code
public static void Main(String[] args)
{
/* 10
/ \
10 3
/ \
10 3
/ \ / \
7 3 42 13
/
7
*/
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(10);
root.right = newNode(3);
root.right.left = newNode(10);
root.right.right = newNode(3);
root.right.left.left = newNode(7);
root.right.left.right = newNode(3);
root.right.right.left = newNode(42);
root.right.right.right = newNode(13);
root.right.right.right.left = newNode(7);
// Print non-zero XOR Paths
printPaths(root);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to Print all the Paths of a
// Binary Tree whose XOR gives a non-zero value
// A Tree node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
// Function to check whether Path
// is has non-zero xor value or not
function PathXor(path)
{
let ans = 0;
// Iterating through the array
// to find the xor value
for (let x = 0; x < path.length; x++)
{
ans ^= path[x];
}
if(ans != 0)
{
return true;
}
else{
return false;
}
}
// Function to print a path
function printPaths(path)
{
for (let x = 0; x < path.length; x++)
{
document.write(path[x] + " ");
}
document.write("</br>");
}
// Function to find the paths of
// binary tree having non-zero xor value
function findPaths(root, path)
{
// Base case
if (root == null)
return;
// Store the value in path vector
path.push(root.key);
// Recursively call for left sub tree
findPaths(root.left, path);
// Recursively call for right sub tree
findPaths(root.right, path);
// Condition to check, if leaf node
if (root.left == null &&
root.right == null)
{
// Condition to check,
// if path has non-zero xor or not
if (PathXor(path))
{
// Print the path
printPaths(path);
}
}
// Remove the last element
// from the path vector
path.pop();
}
// Function to find the paths
// having non-zero xor value
function printpaths(node)
{
let path = [];
findPaths(node, path);
}
/* 10
/ \
10 3
/ \
10 3
/ \ / \
7 3 42 13
/
7
*/
// Create Binary Tree as shown
let root = newNode(10);
root.left = newNode(10);
root.right = newNode(3);
root.right.left = newNode(10);
root.right.right = newNode(3);
root.right.left.left = newNode(7);
root.right.left.right = newNode(3);
root.right.right.left = newNode(42);
root.right.right.right = newNode(13);
root.right.right.right.left = newNode(7);
// Print non-zero XOR Paths
printpaths(root);
</script>
Producción:
10 3 10 7 10 3 3 42
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA