题目描述

给你一棵二叉树的根 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。

解题思路

题目要求将二叉树中每个节点的值替换为所有堂兄弟节点的和，而堂兄弟节点就是指那些和当前节点深度相同但父节点不同的节点。例如下图中，x 的堂兄弟节点是第 n 层除去 x 和 y 的其他所有节点。假设第 n 层所有节点的和为 sum，那么 x 的值应该被替换为 sum−x−y。

在广度优先搜索的过程中，通过第 n−1 层去遍历第 n 层的节点时，可以顺便统计第 n 层节点的和 sum。由于更新 x 的值时需要知道 y 的值（有可能不存在），因此需要通过 n−1 层对第 n 层进行第二次遍历，这时就可以使用 sum−x−y 更新 x 的值了。

在代码实现时，我们需要遍历每一层的节点两次，因此使用动态数组或链表表示的队列会更方便。

参考代码

class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        root.val = 0;
        // 通过队列来
        while(!queue.isEmpty()) {
            // 统计下一层的节点，用于遍历
            Queue<TreeNode> queue2 = new LinkedList<>();
            int sum = 0;
            // 遍历 n-1 层时，统计 n 层的总和 sum
            for(TreeNode fa : queue) {
                if(fa.left != null) {
                    queue2.add(fa.left);
                    sum += fa.left.val;
                }
                if(fa.right != null) {
                    queue2.add(fa.right);
                    sum += fa.right.val;
                }
            }
            for(TreeNode fa : queue) {
                // 当前节点的左右孩子节点之和
                int childSum = (fa.left != null ? fa.left.val : 0)
                + (fa.right != null ? fa.right.val : 0);
                // 将左右孩子的值改为 sum-childSum
                if(fa.left != null) {
                    fa.left.val = sum - childSum;
                }
                if(fa.right != null) {
                    fa.right.val = sum - childSum;
                }
            }
            queue = queue2;
        }
        return root;
    }
}