计算二叉树堂兄弟节点的和

发表于 更新于 分类于 Waline：

这是一道leetcode的中等难度的题目，代码不算复杂，但还是有一点可以记录下来举一反三。

题目描述

题目链接：https://leetcode.cn/problems/cousins-in-binary-tree-ii/description/

给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。

如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。

请你返回修改值之后，树的根 root 。

注意，一个节点的深度指的是从树根节点到这个节点经过的边数。

题目思路

所谓堂兄弟，就是同层的非兄弟节点。

我们的第一步就是要想个办法，筛选出所谓的堂兄弟节点，要做到这一点，要做到两点：

  • 首先是要知道所有的当前节点的同层节点，我们可以用广度优先遍历的改进版，也就是层序遍历，每次遍历一层
  • 其次知道谁是当前节点的兄弟节点，而只有当前节点的父节点知道当前节点的的兄弟节点是谁

所以二者结合起来，就是：

  • 使用层序遍历，每次在遍历第n层的时候，通过第一次遍历第n层节点的所有子节点的方式去收集所有第n+1层的节点，同时计算n+1层所有节点的和，假设为sum
  • 然后再次遍历第n层结点的每一个子节点，这次对于每一个子节点，更新它的值为sum减去，其父节点所有子节点的和

最后需要补充一点，因为每次遍历第n层的时候，更新的是第n+1层的节点，所以根节点没有办法 被更新，有两种处理方式：一种是，直接将根节点的值变为0，因为他没有堂兄弟节点；第二种方式，加一个哨兵节点dummy，将dummy的左子节点指向root，然后从dummy开始进行层序遍历，最后返回dummu.left即可

示例代码

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */


var replaceValueInTree = function(root) {
    const dummy = new TreeNode(0, root);
    const q = [dummy];
    while(q.length) {
        const q2 = [];
        let sum = 0;

        for(const fa of q) {
            if (fa.left) {
                q2.push(fa.left);
                sum += fa.left.val;
            }
            if (fa.right) {
                q2.push(fa.right);
                sum += fa.right.val;
            }
        }

        for(const fa of q) {
            const child_sum = (fa.left ? fa.left.val : 0) + (fa.right ? fa.right.val : 0);

            if (fa.left) {
                fa.left.val = sum - child_sum;
            }

            if (fa.right) {
                fa.right.val = sum - child_sum;
            }
        }

        q.length = 0;
        q.push(...q2);
    }

    return dummy.left;
};