题解 | #Tree I#

题意

给定一个二叉树的bfs序，求每条边两个端点的异或值之和

方法一

我们考虑直接记录i点，与i点的父亲，这样直接计算节点i与其父亲的异或值即可。
因为每个节点有两个儿子，所以每当i+2,他的父亲就会改变(即序号加1)
那么我们就可以按照这个规律维护两个指针计算。

class Solution {
public:
    /**
     * 
     * @param a int整型vector 表示这棵完全二叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    long long tree1(vector<int>& a) {
        int fa = 1;
        int son = 2;
        bool turn = false;
        int n = a.size();
        long long ans = 0;
        for (;son <= n;++ son) {
            ans += a [fa - 1] ^ a [son - 1];    //计算两个端点之间的异或值
            turn = !turn;
            if (!turn) {
                ++ fa;    //i+2,所以父亲也改变了。
            }
        }
        return ans;
    }
};

很显然，由于只遍历了一次a，所以时间复杂度和空间复杂度都为 ,其中n为节点的数量。

方法二(找儿子)

我们考虑每个节点i的连线有哪些？
为了不重复计算，我们只考虑节点i与他的儿子之间的连线。
对于一颗完全二叉树，我们可以知道节点i的左儿子为2i,右儿子为2i+1

所以我们可以直接从1-n遍历i，计算i与儿子之间的异或值。

class Solution {
public:
    /**
     * 
     * @param a int整型vector 表示这棵完全二叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    long long tree1(vector<int>& a) {
        long long ans = 0;
        int length = a.size();
        for (int i = 1;i <= length;++ i) {
            int l_son = i * 2,r_son = i * 2 + 1;
            if (l_son <= length) {
                ans += a [i - 1] ^ a [l_son - 1];    //左儿子存在，就计算值
            }
            if (r_son <= length) {
                ans += a [i - 1] ^ a [r_son - 1];    //右儿子存在
            }
        }
        return ans;
    }
};

很显然，由于只遍历了一次a，所以时间复杂度和空间复杂度与方法一相同，都为 ,其中n为节点的数量。