首页 > 试题广场 >

Tree V

[编程题]Tree V
  • 热度指数：61 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
系统中有一棵n个点的完全二叉树，现给出它的DFS正序遍历序列a_i（即从根节点开始，先遍历左子树，后遍历右子树），请你还原这棵树，并返回加密后的答案。
答案加密方法：所有边两个端点异或的和，即，其中(u_i, v_i)为一条树上的边。

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

示例1

输入

[1,2,3,4,5]

输出

14

说明

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

备注:
数据满足：


算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

树 dfs
难度：
0条回答 813浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号