資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告