Tree I

[编程题]Tree I

热度指数：1874 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

系统中有一棵n个点的完全二叉树，现给出它的BFS层序遍历序列 $a_i$ （从根节点开始，自上而下自左到右的一层一层遍历，即首先访问根，然后从左到右访问第2层上的节点，接着是第三层的节点），请你还原这棵树，并返回加密后的答案。

答案加密方法：所有边两个端点异或的和，即 $\sum\limits_{i=1}^{n-1}u_i\ xor\ v_i$ ，其中 $(u_i, v_i)$ 为一条树上的边。

完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层所有的结点都连续集中在最左边。

样例构成的完全二叉树为：

示例1

输入

[1,2,3,4,5]

输出

说明

树边为(1, 2), (1, 3), (2, 4), (2, 5)，加密过程为(1^2)+(1^3)+(2^4)+(2^5)，答案为18。

备注:

数据满足：

算法知识视频讲解

Java

凯里欧羊

public long tree1 (int[] a) {
        // write code here
        long sum = 0;  // 注意结果要用long，不能用int
        for (int i = 0; i < a.length / 2; i++) {
            if (i * 2 + 1 < a.length) {
                sum += a[i] ^ a[i * 2 + 1];
            }
            if (i * 2 + 2 < a.length) {
                sum += a[i] ^ a[i * 2 + 2];
            }
        }
        return sum;
    }

发表于 2021-08-08 15:45:04 回复(0)

Java

牛客629672613号

* 第i层有i个节点，最后一层除外
* 0
* 1 2
* 3 4 5 6
* 7 8 9 10 11 12 13 14
* 每一行的元素在数组中的索引值
* (i-1)^2 - 1 ~ (i-1)^2 - 1 + 2^(i-1)
* 除第一层外，每一层的每个元素都和上一层的唯一一个元素组成一条边，索引关系：
* n <-------> [(n-1)/2]

* 数组长度为1的需要特殊处理

从数组的最后一个元素遍历，通过上面的关系可以直接定位到和这个元素一条边的上层元素，进行异或元素然后累加

发表于 2020-07-24 15:52:18 回复(0)