系统中有一棵n个点的完全k叉树,现给出它的BFS层序遍历序列(即从根节点开始,每一层从左向右遍历),请你还原这棵树,并返回加密后的答案。
答案加密方法:所有边两个端点异或的和,即,其中为一条树上的边。
下面给出完全二叉树的定义:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k层所有的结点都连续集中在最左边。
请你根据这个定义进行适度推广,得到完全k叉树的含义。
2,[1,2,3,4,5]
18
树边为(1, 2), (1, 3), (2, 4), (2, 5),加密过程为(1^2)+(1^3)+(2^4)+(2^5),答案为18。样例1构成的完全二叉树为:
3,[1,2,3,4,5]
17
树边为(1, 2), (1, 3), (1, 4), (2, 5),加密过程为(1^2)+(1^3)+(1^4)+(2^5),答案为17。样例2构成的完全三叉树为:
数据满足:
这道题你会答吗?花几分钟告诉大家答案吧!