原文:
给定一个二叉树，任务是打印该树的所有根到叶路径，其 xor 值为非零。
示例:
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.
方法: 为了解决上述问题，主要思想是遍历树，检查该路径中所有元素的异或是否为零。
- 我们需要使用 递归遍历树。
- 对于每个节点，继续计算从根到当前节点的路径的异或。
- 如果节点是左边的叶节点，并且当前节点的右边的子节点为空，那么我们检查路径的 xor 值是否非零，如果非零，那么我们打印整个路径。
下面是上述方法的实现:
c
// c program to print all the paths of a
// binary tree whose xor gives a non-zero value
#include
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& 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& 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& 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 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 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 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 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 path = new vector();
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
python 3
# 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 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 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 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 path = new list();
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
java 描述语言
output:
10 3 10 7
10 3 3 42
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
