题目的主要信息：
- 一棵n个节点的完全二叉树，其dfs正序遍历（先左后右dfs）序列记录在a数组中
- 还原这棵树并返回加密后的答案，加密方式为这棵树的所有边的两个端点权值进行异或运算，然后全部相加
- 完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。
方法一：父到子的边计算
具体做法：
对于完全二叉树，我们如果如果知道总节点个数，就会知道左子树和右子树分别有多少节点：
这是左子树是满二叉树的情况。
这是右子树为满二叉树的情况。
得到了各个子树的个数，根据dfs的遍历顺序，我们就可以得到每个节点在数组a中的下标，对于以某个节点为根节点的子树而言，数组其前部半分就是左子树，数组后半部分就是右子树。因此我们可以递归考虑每一个节点，计算其左右子树节点数，如果它的左子树不为空，我们将其与左子树第一个节点做异或加到答案中（因为这就是它的左子节点），然后递归进入以左子节点为根的这棵子树（通过控制下标边界，因为刚刚得到这棵树的节点数，因此它在数组a中的左右界可以得到）；如果它的右子树不为空，同左子树的处理方式。这里我们没必要先左后右，因为我们控制了每棵子树在数组a中的下标左右界。
class Solution {
public:
void deep_to_count(int n, vector<int>& res){ //计算左右子树节点数
int i = 0;
while (!(pow(2, i) <= n && pow(2, i + 1) > n)) //直接找到最深的一层
i++;
if(pow(2, i) - 1 + pow(2, i - 1) - 1 >= n - 1){ //右子树满
res[1] = pow(2, i - 1) - 1;
res[0] = n - 1 - res[1];
}else{ //左子树满
res[0] = pow(2, i) - 1;
res[1] = n - 1 - res[0];
}
}
void encipher(int begin, int end, vector<int>& a, long long& res){
int root = a[begin]; //子树的根
int n = end - begin; //以root为根的子树节点数
vector<int> count(2, 0);
if(n == 0) //空结点直接返回
return;
deep_to_count(n, count); //根据深度计算左右子树节点数
if(count[0] != 0){ //左子树不为空
res += root ^ a[begin + 1];
encipher(begin + 1, begin + count[0] + 1, a, res); //递归左子树
}
if(count[1] != 0){ //右子树不为空
res += root ^ a[begin + count[0] + 1];
encipher(begin + count[0] + 1, end, a, res); //递归右子树
}
}
long long tree5(vector<int>& a) {
long long res = 0;
encipher(0, a.size(), a, res); //加密函数
return res;
}
};复杂度分析：
- 时间复杂度：
，加密函数相当于dfs，遍历二叉树的每一个节点，对于每个节点，我们采用计算深度的方式计算左右子树的节点数，每次花费
- 空间复杂度：
，完全二叉树，递归栈深度最大为
方法二：子到父的边计算
具体做法：
刚刚方法一我们利用的是完全二叉树左右子树个数的性质，现在我们利用完全二叉树层次遍历的性质。我们都知道，完全二叉树层次遍历的时候对于第个节点，其父节点为
，而第
个节点的子节点一定是
和
，因此我们可以用两个下标，一个利用乘
的方式来记录其层次遍历的序号，一个正常先左后右的方式记录dfs的序号，前者我们可以对
和
求异或，求遍每一条边，后者记录相应权值在数组a中的位置。
class Solution {
public:
void dfs(int cur, int& index, vector<int>& a, long long& res, vector<int>& w){
if(cur > a.size()) //直到数组a长度结束
return;
w[cur] = a[index]; //下标要比这个点小一个，记录该节点权值
index++;
if(cur != 1)
res += w[cur] ^ w[cur / 2]; //不为根时，计算其与父节点的加密
dfs(cur * 2, index, a, res, w); //dfs递归，先左后右
dfs(cur * 2 + 1, index, a, res, w);
}
long long tree5(vector<int>& a) {
long long res = 0;
int index = 0; //记录下标,dfs遍历到的第几个数
vector<int> w(a.size() + 1, 0); //n个节点的权值，按照层次遍历的次序
dfs(1, index, a, res, w);
return res;
}
};复杂度分析：
- 时间复杂度：
，二叉树每个节点只遍历一次
- 空间复杂度：
，递归栈深度同方法一最大为
，故舍去低次幂
京公网安备 11010502036488号