lc2445
hash预处理query，利用小的数不可能被大的数影响的单调性dfs
class Solution {
public:
int numberOfNodes(int n, vector<int>& queries) {
map<int, int> cnt;
for (auto& q: queries) cnt[q]++;
function<int(int, int)> dfs = [&] (int node, int c) -> int {
if (node > n) return 0;
int nc = (c + cnt[node]) % 2;
int ans = nc;
//遍历 累加对子树的翻转次数 处理
ans +=dfs(node * 2, nc);
ans += dfs(node * 2 + 1, nc);
return ans;
};
return dfs(1, 0);
}
};
dfs序+差分
dfs遍历给二叉树的每个节点标记连续的编号，再用差分数组统计每个节点被翻转的次数，最后统计被翻转奇数次（即最终为1）的节点数量
1. 利用dfs序将子树映射到一段连续的区间
2. 翻转区间可以用异或来进行差分
#include <vector>
#include <numeric>
using namespace std;
class Solution {
private:
int dfsId;
// 深搜遍历，记录每个节点的dfs起始/结束id
void dfs(int cur, int pre, vector<vector<int>>& adjList, vector<int>& starts, vector<int>& ends) {
starts[cur] = dfsId;
for (int next : adjList[cur]) {
if (next != pre)
dfs(next, cur, adjList, starts, ends);
}
ends[cur] = dfsId;
dfsId++;
}
public:
int numberOfNodes(int n, vector<int>& queries) {
// 构建邻接表（0为根节点，原问题1-based转0-based）
vector<vector<int>> adjList(n);
for (int cur = 1; cur < n; cur++) {
int parent = (cur - 1) / 2;
adjList[parent].push_back(cur);
adjList[cur].push_back(parent);
}
// 初始化dfs相关数组
vector<int> starts(n, 0), ends(n, 0);
dfsId = 0;
dfs(0, -1, adjList, starts, ends);
// 差分数组处理翻转操作（异或实现翻转）
vector<int> diff(n + 1, 0);
for (int node : queries) {
int u = node - 1; // 1-based转0-based
int l = starts[u], r = ends[u];
diff[l] ^= 1;
if (r + 1 <= n)diff[r + 1] ^= 1;
}
// 求差分前缀异或，统计最终为1的节点数
int cnt = 0, curXor = 0;
for (int i = 0; i < n; i++) {
curXor ^= diff[i];
cnt += curXor & 1;
}
return cnt;
}
};
