2641. 二叉树的堂兄弟节点 II - Java 广度优先搜索 两次 BFS +一次 BFS 优化
6335. 二叉树的堂兄弟节点 II
原题地址：https://leetcode.cn/problems/cousins-in-binary-tree-ii/
题解
堂兄节点是指这一层中除自己和兄弟节点外的其他节点，我们记录下每一层所有节点的和，然后用和减去自己和兄弟节点的值即可得到该节点的修改值
朴素思路：两轮BFS
如何记录层次/广度/深度：用cnt记录下当前广度的节点数，在BFS循环while(!queue.isEmpty())内套一个内层循环while(cnt)，当内层循环遍历完毕后，理所当然地，队列里剩下的节点全都是下一个广度的节点，所以在下一次循环时直接cnt=queue.size()即可
第一次BFS用sum记录下该层所有节点的和，推入List，通过上述办法实现层次的迭代
第二次BFS由于要考虑到兄弟节点的问题，我们不能直接在遍历到节点的时候计算它自己的值，因此每次遍历到节点时计算其子节点的值，即当前节点深度为floor时
当然，由于直接修改node.left的值会影响后面node.right的值的计算，所以我们先用两个tmp变量存下来计算结果，等两个子节点都计算完毕后再去更新
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public TreeNode replaceValueInTree(TreeNode root) {
List<Integer> floorsum=new LinkedList<>();
Queue<TreeNode> queue=new LinkedList<>();
int floor=0,cnt,sum;
TreeNode node;
queue.add(root);
while(!queue.isEmpty()){
cnt=queue.size();
sum=0;
while(cnt>0){
node=queue.remove();
sum+=node.val;
if(node.left!=null)queue.add(node.left);
if(node.right!=null)queue.add(node.right);
cnt--;
}
floorsum.add(sum);
floor++;
}
floor=0;
root.val=0;
int lefttmp=0,righttmp=0;
queue.add(root);
while(!queue.isEmpty()){
cnt=queue.size();
while(cnt>0){
node=queue.remove();
if(node.left!=null){
lefttmp=floorsum.get(floor+1)-node.left.val-(node.right==null?0:node.right.val);
queue.add(node.left);
}
if(node.right!=null){
righttmp=floorsum.get(floor+1)-node.right.val-(node.left==null?0:node.left.val);
queue.add(node.right);
}
if(node.left!=null){
node.left.val=lefttmp;
}
if(node.right!=null){
node.right.val=righttmp;
}
cnt--;
}
floor++;
}
return root;
}
}
|
简化思路：一轮BFS
我们有没有可能在一轮BFS内解决：计算该层节点和并计算每个节点的值呢？考虑一下为了实现这个效果我们需要解决的问题
首先我们仍然需要每一层遍历两次：
但是当当前节点所在层计算完节点和后，计算节点值遇到了一个问题：就像上面所说的，我们需要其父节点来获取其兄弟结点的值
那么我们可以当遍历到第i层时，去计算第i+1层的节点和，并更新第i+1层的节点的值，这样就不会遇到这个问题了
我们上面说过需要在计算完全部节点的和后才能开始计算各节点的值，所以不可避免需要两轮循环操作才能完成一层节点的更新，需要用一个临时的队列tmpQueue来记录下该层的节点
- 第一次循环从queue取出节点时进行操作再将其推入tmpQueue
- 第二次循环再从tmpQueue中取出节点进行第二轮操作
具体一点就是：
- 第一次循环：
- 从queue中取出节点
- 根据节点计算其子节点那一层的节点和
- 将节点再推入tmpQueue
- 当queue中该层节点被全部取出（cnt==0）后，节点和计算完毕
- 第二次循环：
- 从tmpQueue中取出节点
- 根据计算完的节点和计算其子节点的值并更新
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public TreeNode replaceValueInTree(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
Queue<TreeNode> tmpQueue=new LinkedList<>();
int cnt,sum;
int lefttmp=0,righttmp=0;
TreeNode node;
queue.add(root);
root.val=0;
while(!queue.isEmpty()){
cnt=queue.size();
sum=0;
while(cnt>0){
node=queue.remove();
tmpQueue.add(node);
if(node.left!=null){
sum+=node.left.val;
queue.add(node.left);
}
if(node.right!=null){
sum+=node.right.val;
queue.add(node.right);
}
cnt--;
}
while(!tmpQueue.isEmpty()){
node=tmpQueue.remove();
if(node.left!=null){
lefttmp=sum-node.left.val-(node.right==null?0:node.right.val);
}
if(node.right!=null){
righttmp=sum-node.right.val-(node.left==null?0:node.left.val);
}
if(node.left!=null){
node.left.val=lefttmp;
}
if(node.right!=null){
node.right.val=righttmp;
}
}
}
return root;
}
}
|
