我要招人

去企业版

首页 > 试题广场 >

Tree I

[编程题]Tree I

热度指数：1829 时间限制：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。

备注:

数据满足：

算法知识视频讲解

heyJulian

/**
 * 
 * @param a int整型一维数组 表示这棵完全二叉树的Bfs遍历序列的结点编号
 * @param aLen int a数组长度
 * @return long长整型
 */
long long tree1(int* a, int aLen ) {
    long long sum = 0;
    //性质：若下标从0开始，第i个结点的左孩子为2*i+1，右孩子为2*(i+1)
    for(int i=0;i<aLen/2;i++){
       sum+=(a[i]^a[2*i+1]);
       if((2*(i+1))<aLen) sum+=a[i]^a[2*(i+1)];//可能没有右孩子结点
    }
    return sum;
}

发表于 2020-07-22 20:59:37 回复(0)

勇敢牛牛，不怕困难！

typedef long long LL;
typedef struct TreeNode* PTreeNode;

PTreeNode buildTree(int* a, const int aSize, int idx) {
  if (idx >= aSize) return NULL;
  PTreeNode root = (PTreeNode) malloc(sizeof(struct TreeNode));
  root->val   = *(a + idx);
  root->left  = buildTree(a, aSize, idx << 1 | 1);
  root->right = buildTree(a, aSize, (idx << 1) + 2);
  return root;
}

void xorSum(PTreeNode root, PTreeNode parent, LL* ans) {
  if (parent)      *ans += parent->val ^ root->val;
  if (root->right) xorSum(root->right, root, ans);
  if (root->left)  xorSum(root->left,  root, ans);
}
/**
 * 
 * @param a int整型一维数组 表示这棵完全二叉树的Bfs遍历序列的结点编号
 * @param aLen int a数组长度
 * @return long长整型
 */
LL tree1(int* a, int aLen) {
  PTreeNode root = buildTree(a, aLen, 0);
  if (!root) return 0;
  
  LL ans = 0;
  xorSum(root, NULL, &ans);
  return ans;
}

发表于 2021-07-17 12:15:50 回复(0)

牛客377646584号

class Solution:
def tree1(self , a ):
# write code here
ans = 0
for i in range(1,len(a)+1):
if i*2-1<len(a):
ans+=a[i-1]^(a[i*2-1])
if i*2 <len(a):
ans+=a[i-1]^a[i*2]
return ans

发表于 2021-09-09 14:23:47 回复(0)

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)

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)

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)