题解 | #Tree V#

class Solution {
public:
/**
*
* @param a int整型vector 表示这棵完全二叉树的Dfs遍历序列的结点编号
* @return long长整型
*/
long long tree5(vector<int>& a) {
// write code here
int len = a.size();
long long ans = 0;
cal(a, 0, len, ans);
return ans;
}</int>

void cal(vector<int>&a, int beg, int end, long long &ans){
    int len = end - beg;
    int root = a[beg];
    //确定层数
    auto it = cal_level(len);
    if(it.first != 0){
        int tmp = root ^ a[beg + 1];
        ans += tmp;
        cal(a, beg + 1, beg + it.first + 1, ans);
    }

    if(it.second != 0){
        int tmp = root ^ a[beg + it.first + 1];
        ans += tmp;
        cal(a, beg + it.first + 1, end, ans);
    }
}
//计算左右子树长度
pair<int,int> cal_level(int len){
    int level = 0;
    int left = 0, right = 0;
    for(int i = 0;i < 30; ++i){
        if(pow(2, i) <= len && pow(2, i + 1) > len){
            level = i;
            break;
        }
    }
    if(pow(2, level) - 1 + pow(2, level - 1) - 1 >= len - 1){
        right = pow(2, level - 1) - 1;
        left = len - 1 - right;
    }else{
        left = pow(2, level) - 1;
        right = len - 1 - left;
    }
    pair<int, int>ans(left,right);
    return ans;
}

};