极客笔记C++ 计算从根节点到叶子节点的所有边的按位异或等于K的节点数
计算从根节点到给定树中节点的路径上所有边的按位异或等于给定值K的节点数量。这被称为计算从根节点到叶子节点的所有边的按位异或等于K的节点的问题。这个有趣的话题涉及到在穿越树时有效地计算从根节点到叶子节点的每条路径上的异或值。在本文中，我们将介绍一些解决这个问题的方法，包括Trie数据结构、前缀异或数组和深度优先搜索。每种方法都为有效计算这样的节点提供了独特的见解，并为解决包括树在内的相关问题提供了有用的方法。
使用的方法
- 深度优先搜索（DFS）
-
前缀异或数组
-
Trie数据结构
深度优先搜索（DFS）
使用这种方法，我们通过深度优先搜索穿越树，同时跟踪从根节点到当前节点的所有边的异或值。遍历过程中遇到的每个异或值都被记录在哈希表中。在每个节点，我们要检查哈希表是否包含当前路径异或值与K的异或值。如果是，计数将增加，因为在路径上存在与当前节点的异或值为K的节点。然后，DFS遍历将继续查看其他路径。
步骤
- 从头开始建立一个哈希表，用于跟踪在DFS遍历过程中遇到的异或值的数量。
-
使用深度优先搜索遍历树，同时记录从根节点到当前节点的每条边的异或值。
-
实际检查每个节点，检查哈希表是否包含当前路径异或值与K的异或值。如果是，适当增加计数。
-
递归地探索当前节点的每个孩子，根据需要更改当前路径的异或值。
-
当遍历完成时，计数将反映出从根节点到叶子节点的所有边的按位异或等于K的节点数量。
-
时间复杂度为O(N)，其中N是树中的节点数。
示例
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<int, vector<int>> graph;
unordered_map<int, int> xorCount;
void addEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfs(int node, int parent, int xorValue, int k) {
xorValue ^= node;
if (xorCount.find(xorValue ^ k) != xorCount.end())
xorCount[xorValue ^ k]++;
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node, xorValue, k);
}
}
}
int main() {
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
int k = 3;
xorCount[0] = 1;
dfs(1, -1, 0, k);
cout << "Count of nodes whose XOR of all edges leading to root equals " << k << ": ";
cout << xorCount[k] << endl;
return 0;
}
输出
Count of nodes whose XOR of all edges leading to root equals 3: 0
滑动窗口方法
在这种方法中，使用前缀异或数组快速计算根节点到特定节点的所有路径上的所有边的异或值。当我们深入树中时，我们使用深度优先搜索方法计算前缀异或值。我们确定前缀异或数组是否具有当前路径的异或值与K的异或值。如果是，则相应地增加计数。
步骤
- 从头开始创建一个前缀异或数组，并将每个节点连接到根节点的所有边的异或值填充到数组中。
-
使用深度优先搜索遍历，下降树同时刷新前缀异或数组。
-
检查每个节点以查看前缀异或数组是否包含当前路径的异或值与K的异或值。如果是，则相应地增加计数。
-
通过递归探索当前节点的每个子节点来更新前缀异或数组。
-
当遍历完成时，计数将反映出所有边引导到根节点的位异或等于K的节点的数量。时间复杂度为O(N)，其中N是树中的节点数量。
示例
#include <iostream>
#include <vector>
using namespace std;
void dfs(int node, int parent, const vector<vector<int>>& graph,
vector<int>& prefixXOR, int currentXOR) {
prefixXOR[node] = currentXOR;
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node, graph, prefixXOR, currentXOR ^ child);
}
}
}
void countXORPaths(int node, int parent, const vector<vector<int>>& graph, const vector<int>& prefixXOR, int K, int& count) {
if (prefixXOR[node] == K)
count++;
for (int child : graph[node]) {
if (child != parent) {
countXORPaths(child, node, graph, prefixXOR, K, count);
}
}
}
int main() {
int n = 6;
int root = 0;
vector<vector<int>> graph(n);
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0, 5};
vector<int> prefixXOR(n, 0);
dfs(root, -1, graph, prefixXOR, 0);
int K = 2;
int count = 0;
countXORPaths(root, -1, graph, prefixXOR, K, count);
cout << count << endl;
return 0;
}
输出
2
Trie数据结构
在这种方法中，遍历过程中遇到的前缀异或值会存储在Trie数据结构中。我们在每个节点上确定Trie是否包含当前路径异或与K的值。如果是，我们适当地增加计数。Trie有效地处理异或运算，并使我们能够快速确定所需的异或值。
步骤
- 创建一个新的空Trie数据结构实例，用于保存遍历过程中遇到的任何前缀异或值。
-
执行深度优先搜索遍历树，在向下遍历树时使用前缀异或值更新Trie。
-
检查每个节点，看看Trie是否包含当前路径异或与K的值。如果是，适当增加计数。
-
递归地检查当前节点的每个子节点，同时更新Trie。
-
当遍历完成时，计数将反映出所有边导向根部的节点的位异或等于K的数量。
-
时间复杂度为O(N)，其中N是树中节点的数量。
示例
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TrieNode {
unordered_map<int, TrieNode*> children;
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(int num) {
TrieNode* curr = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (curr->children.find(bit) == curr->children.end())
curr->children[bit] = new TrieNode();
curr = curr->children[bit];
}
}
bool search(int num) {
TrieNode* curr = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (curr->children.find(1 - bit) != curr->children.end())
curr = curr->children[1 - bit];
else
curr = curr->children[bit];
}
return true;
}
private:
TrieNode* root;
};
struct TreeNode {
int val;
vector<TreeNode*> children;
};
int countPrefixXOR(TreeNode* root, Trie& trie, int curXOR, int targetXOR) {
curXOR ^= root->val;
trie.insert(curXOR);
int count = trie.search(curXOR ^ targetXOR);
for (TreeNode* child : root->children) {
count += countPrefixXOR(child, trie, curXOR, targetXOR);
}
return count;
}
int main() {
// Sample Tree Creation
TreeNode* root = new TreeNode();
root->val = 1;
TreeNode* node1 = new TreeNode();
node1->val = 0;
root->children.push_back(node1);
TreeNode* node2 = new TreeNode();
node2->val = 1;
root->children.push_back(node2);
TreeNode* node3 = new TreeNode();
node3->val = 0;
node1->children.push_back(node3);
TreeNode* node4 = new TreeNode();
node4->val = 1;
node1->children.push_back(node4);
TreeNode* node5 = new TreeNode();
node5->val = 1;
node2->children.push_back(node5);
int K = 5;
Trie trie;
int result = countPrefixXOR(root, trie, 0, K);
cout << "The count of nodes with prefix XOR equal to K is: " <<
result << endl;
return 0;
}
输出
The count of nodes with prefix XOR equal to K is: 6
结论
所有三种方法都能有效地计算出从根节点到所有边的按位异或大于或等于K的节点数。选择的方法取决于特定的需求、可访问的数据结构和树的大小。深度优先搜索技术简单直观，易于使用，但对于大型树可能不是最佳选择。在性能至关重要的应用中，前缀异或数组和字典树方法更为有效，因为它们在处理更大的树时提供了常数时间复杂度的异或操作。