【牛客编程巅峰赛S1第4场】Tree I

题目

系统中有一棵 $n$ 个点的完全二叉树，现给出它的 BFS 层序遍历序列 $a_i$ ，请还原这棵树，并返回加密后的答案。
答案加密方法：所有边两个端点异或的和，即 $\sum\limits_{i=1}^{n-1}u_i\ xor\ v_i$ ，其中 $(u_i, v_i)$ 为一条树上的边。

解题思路

将完全二叉树按照层次遍历的顺序从 1 开始编号，则节点 $i$ 的左孩子节点为 $2i$ ，右孩子节点为 $2i+1$ ，所以 $(a[i], a[2i])$ 和 $(a[i], a[2i+1])$ 是树上的边，计算每条边的两个端点的异或值，累加后返回答案。

C++代码

class Solution {
public:
    /**
     * 
     * @param a int整型vector 表示这棵完全二叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    long long tree1(vector<int>& a) {
        // write code here
        int n = a.size();
        long long ans = 0;
        for(int i=1; i<=n; ++i){
            int left = i<<1;
            int right = left + 1;
            if(left <= n){
                ans += a[i-1] ^ a[left-1];
            }
            if(right <= n){
                ans += a[i-1] ^ a[right-1];
            }
        }
        return ans;
    }
};