题目描述
给你一棵二叉树的根 root
,请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和。
如果两个节点在树中有相同的深度且它们的父节点不同,那么它们互为 堂兄弟。
请你返回修改值之后,树的根 root
。
注意,一个节点的深度指的是从树根节点到这个节点经过的边数。
样例
输入:root = [5,4,9,1,10,null,7]
输出:[0,0,0,7,7,null,11]
解释:上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 5 的节点没有堂兄弟,所以值修改为 0。
- 值为 4 的节点没有堂兄弟,所以值修改为 0。
- 值为 9 的节点没有堂兄弟,所以值修改为 0。
- 值为 1 的节点有一个堂兄弟,值为 7,所以值修改为 7。
- 值为 10 的节点有一个堂兄弟,值为 7,所以值修改为 7。
- 值为 7 的节点有两个堂兄弟,值分别为 1 和 10,所以值修改为 11。
输入:root = [3,1,2]
输出:[0,0,0]
解释:上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 3 的节点没有堂兄弟,所以值修改为 0。
- 值为 1 的节点没有堂兄弟,所以值修改为 0。
- 值为 2 的节点没有堂兄弟,所以值修改为 0。
限制
- 树中节点数目的范围是
[1, 10^5]
。 1 <= Node.val <= 10^4
算法
(层级遍历) $O(n)$
- 层级遍历,每次求出下一层的总和,假设为 $tot$,然后对于当前元素 $u$,其左右儿子的值修改为 $tot$ 减去左右儿子的值。
时间复杂度
- 每个元素进队一次,出队一次,在队列中被访问一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储层级遍历的数据结构。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* replaceValueInTree(TreeNode* root) {
vector<TreeNode*> q1, q2;
q1.push_back(root);
root->val = 0;
while (!q1.empty()) {
int tot = 0;
for (auto u : q1) {
if (u->left) {
tot += u->left->val;
q2.push_back(u->left);
}
if (u->right) {
tot += u->right->val;
q2.push_back(u->right);
}
}
for (auto u : q1) {
int r = tot;
if (u->left) r -= u->left->val;
if (u->right) r -= u->right->val;
if (u->left) u->left->val = r;
if (u->right) u->right->val = r;
}
q1 = q2;
q2.clear();
}
return root;
}
};