[题解] Tree V
考察点：完全二叉树的含义，Dfs序列遍历顺序
需要理解完全二叉树的含义：即每个结点的子结点之多有两个子结点。
不妨我们先考虑最简单的一种情况，即结点编号按照一棵“标准”完全二叉树给出，即结点的两个子结点分别为
与
，根据这棵树，我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。
实际上，我们可以利用上述方法来对这棵树进行Dfs搜索，并且按照搜索顺序记录Dfs序的编号，并对应到所给的Dfs序数组上，然后计算加密后的答案即可。
时间复杂度，空间复杂度
参考代码：
class Solution {
public:
int n, d[100010];
long long ans = 0, cnt = 1;
inline void dfs(int x, int p) {
if ((x << 1) <= n) {
++cnt;
ans += (d[p] ^ d[cnt]);
dfs(x << 1, cnt);
}
if ((x << 1 | 1) <= n) {
++cnt;
ans += (d[p] ^ d[cnt]);
dfs(x << 1 | 1, cnt);
}
}
long long tree5(vector<int> &a) {
n = a.size();
for (int i = 0; i < n; ++i) {
d[i + 1] = a[i];
}
dfs(1, 1);
return ans;
}
}; 
投递作业帮等公司8个岗位 >
查看21道真题和解析