Tree I

[编程题]Tree I

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

备注:

数据满足：

算法知识视频讲解

勇敢牛牛，不怕困难！

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)