数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中二叉树任意两节点路径的异或值
在这个问题中，我们给定一棵二叉树和二叉树中的两个节点。我们的任务是打印这两个节点之间路径上的所有节点的异或值。
让我们举个例子来理解这个问题：
我们需要找到节点2和节点3之间的所有节点的异或值。
从节点2到节点3的路径为：2 → 6 → 1 → 3。
我们将计算 2^3^1^3。
**输出** -
为了解决这个问题，我们需要找到从一个节点到另一个节点的路径。为此，我们将找到从根节点到这两个节点的路径上所有节点的异或值。在这样做时，从根节点遍历时存在两种情况，即源节点和目标节点都位于根节点的同一侧，或者它们位于根节点的不同侧。在第一种情况下，路径之外的所有节点将被遍历两次并抵消。而在前一种情况下，需要考虑从根节点到节点的整个路径。在每一步中，我们将找到节点与其之前找到的异或结果的异或值，这将节省空间。
示例
展示我们解决方案实现的程序：
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* getNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void pathStoD(Node* root, unordered_map<int, int>& path, int XOR){
if (!root)
return;
path.insert(make_pair(root->data, XOR ^ root->data));
XOR ^= root->data;
if (root->left)
pathStoD(root->left, path, XOR);
if (root->right)
pathStoD(root->right, path, XOR);
}
int findPathXOR(unordered_map<int, int> path, int node1, int node2){
return path[node1] ^ path[node2];
}
int main(){
struct Node* root = getNode(1);
root->left = getNode(6);
root->left->left = getNode(2);
root->left->right = getNode(4);
root->right = getNode(3);
root->right->left = getNode(7);
root->right->right = getNode(5);
int XOR = 0;
unordered_map<int, int> mp;
int source = 2;
int destination = 3;
pathStoD(root, mp, XOR);
cout<<"The XOR of all node from "<<source<<" to "<<destination<<" of the tree is : ";
cout<<findPathXOR(mp, source, destination);
return 0;
}输出
The XOR of all node from 2 to 3 of the tree is : 7
更新于: 2020年4月20日
248 次浏览
广告