题意：

给定一棵完全二叉树按照层次遍历的访问序列，对于这棵树的每条边，所表示的价值为这条边两点序号的异或值，求出整棵树所有边的价值和。

解法一（记录父节点）

我们用一个变量 $i$ 表示当前枚举到的节点下标（从左到右枚举）， $i$ 从 $1$ 开始枚举

用一个变量 $j$ 表示当前下标为 $i$ 所代表的节点的父亲节点的下标， $j$ 显然刚开始为 $0$

如下图：

我们的变量 $i$ 是从左到右枚举的，变量 $j$ 显然也是从左到右枚举

我们发现，变量 $i$ 每枚举了两个节点，变量 $j$ 刚好枚举了一个节点

于是我们可以记录下当前已经访问了多少个节点，每访问两个节点后让变量 $j$ 加上 $1$

于是我们就做完了

代码：

class Solution {
public:
    long long tree1(vector<int>& a) {
        long long ans=0;
        for(int i=1,j=0,c=0;i<a.size();i++){
            //i为当前节点，j为当前节点父节点
            //c为从第二个开始已经访问的节点个数
            c++;
            ans+=a[i]^a[j];
            if(c%2==0)j++;//每访问两个加一次
        }
        return ans;
    }
};

时间复杂度： $O(n)$ ，程序中循环体执行了 $n-1$ 次，循环体中的时间复杂度是 $O(1)$ 的，故总的时间复杂度为 $O(n)$

空间复杂度： $O(n)$ ，程序中存储了一个有 $n$ 个整型元素的数组，还有若干个整型或长整型变量，故总的空间复杂度为 $O(n)$

解法二（找节点下标规律）：

我们观察如下完全二叉树（编号从 $1$ 开始）

我们很容易发现，若当前节点编号为 $k$ ，则当前节点的左儿子编号为 $2*k$ ，当前节点的右儿子编号为 $2*k+1$

但是题目中的数组下标是从 $0$ 开始的，我们可以把所有的计算完后的编号整体向左移动一位

于是我们就做完了（注意判断超界）

代码：

class Solution {
public:
    long long tree1(vector<int>& a) {
        long long ans=0;
        for(int k=1;k<=a.size();k++){
            //k为当前节点
            if(k*2-1<a.size()){//左儿子
                ans+=a[k-1]^a[k*2-1];
            }
            if(k*2+1-1<a.size()){//右儿子
                ans+=a[k-1]^a[k*2+1-1];
            }
        }
        return ans;
    }
};

时间复杂度： $O(n)$ ，程序中循环体共执行了 $n$ 次，循环体内部的时间复杂度是 $O(1)$ 的，故总的时间复杂度是 $O(n)$

空间复杂度： $O(n)$ ，程序中存储了一个有 $n$ 个整型元素的数组，还有若干个整型或长整型变量，故总的空间复杂度为 $O(n)$

题解 | #Tree I#

题意：

解法一（记录父节点）

解法二（找节点下标规律）：