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。

备注:

数据满足：

算法知识视频讲解

Python

Ice&雪

import math

class Solution:

def tree1(self, a):

# write code here

n = int(math.log(len(a), 2)) + 1 ## 求层数

dic = {} ## 将每一层存入字典

k = 0

for i in range(n):

dic[i + 1] = a[: (2 ** i)]

if i != 0:

for j in range(len(dic[i + 1])): ## 跟据子节点层找父节点

k += dic[i][int(j / 2)] ^ dic[i + 1][j]

a = a[(2 ** i) :]

return k

发表于 2025-01-23 15:50:08 回复(0)

Python

牛客540732497号

... ...

idxi ...

/ \

idxj idxk

... ...

idxj = 2*idxi + 1

idxl = 2*idxi + 2

需要特别讨论的是 idxk是否存在，存在的话(idxk <= len(a) - 1)，需要计算idexi ^ idxj 以及 idxi ^ idxk。不存在的话，只需要计算idexi ^ idxj

class Solution:
    def tree1(self , a ):
        sumTree = 0
        i = 0
        while (2*i+2) <= len(a):
            sumTree += a[i] ^ a[2*i+1]
            if (2*i+2) <= len(a)-1:
                sumTree += a[i] ^ a[2*i+2]
            i += 1
        return sumTree

发表于 2020-08-07 12:32:08 回复(0)