首页 > 试题广场 >

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。

备注:
数据满足：


算法知识视频讲解
开通博客
头像 牛客890440093号
发表于 2021-09-08 12:25:04
class Solution {public: /** * * @param a int整型vector 表示这棵完全二叉树的Dfs遍历序列的结点编号 * @return long长整型 */ long long tree5(vector<int&g 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 呆喵挠琴
发表于 2021-10-23 18:40:18
题目的主要信息： 已知完全二叉树的DFS正序遍历序列 求所有边两个端点异或的和 方法一：DFS 题目告诉我们这棵树是完全二叉树，根据完全二叉树的性质，对于编号为i的节点，它的左孩子的编号为2i，右孩子的编号为2i+1。因此我们可以根据这个性质，从根节点开始，通过性质得到左右孩子的编号，计算孩子和 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-09-17 21:46:07
题目的主要信息： 一棵n个节点的完全二叉树，其dfs正序遍历（先左后右dfs）序列记录在a数组中 还原这棵树并返回加密后的答案，加密方式为这棵树的所有边的两个端点权值进行异或运算，然后全部相加 完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 George_Plover
发表于 2021-09-14 22:43:12
题解 题意整理： 基本题意 ​ 给出一棵大小为 nnn 的完全二叉树的前序遍历序列 {ai}\{a_i\}{ai​} 。 ​ 定义树上任意一条边，若其连接 (u,v)(u,v)(u,v) 两个点，则其边权为 u<mtext> xor </mtext>v 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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