二叉树的堂兄弟节点 II

难度: Medium

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

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

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

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

示例 1：

输入：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 。

示例 2：

输入：root = [3,1,2]
输出：[0,0,0]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 3 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点没有堂兄弟，所以值修改为 0 。
- 值为 2 的节点没有堂兄弟，所以值修改为 0 。

提示：

树中节点数目的范围是 [1, 10⁵] 。
1 <= Node.val <= 10⁴

Submission

运行时间: 319 ms

内存: 54.9 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs1(node: Optional[TreeNode], depth: int):
            if node is None:
                return
            if len(dSum) == depth:
                dSum.append(0)
            dSum[depth] += node.val
            dfs1(node.left, depth + 1)
            dfs1(node.right, depth + 1)
        def dfs2(node: Optional[TreeNode], depth: int):
            childSum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
            depth += 1
            if node.left:
                node.left.val = dSum[depth] - childSum
                dfs2(node.left, depth)
            if node.right:
                node.right.val = dSum[depth] - childSum
                dfs2(node.right, depth)
        dSum = []
        dfs1(root, 0)
        root.val = 0
        dfs2(root, 0)
        return root

Explain

该题解采用了深度优先搜索算法（DFS）来解决问题。分为两个主要步骤： 1. 首先，通过第一个DFS（函数dfs1）遍历整棵树并计算出每一层所有节点值的总和，这些总和保存在dSum列表中。每个索引i对应的dSum[i]表示第i层所有节点的值的总和。 2. 第二个DFS（函数dfs2）用于更新每个节点的值。在这个阶段，对于每个节点，我们计算其所有堂兄弟节点值的总和。这通过从当前层总和中减去该节点直接子节点的值来实现。这种计算保证了节点值被替换为所有堂兄弟的值的和。整个过程确保了每个节点都被正确地替换为其堂兄弟节点的值之和，满足题目要求。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         this.val = val
#         this.left = left
#         this.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs1(node: Optional[TreeNode], depth: int):
            if node is None:
                return
            if len(dSum) == depth:
                dSum.append(0)
            dSum[depth] += node.val
            dfs1(node.left, depth + 1)
            dfs1(node.right, depth + 1)
        def dfs2(node: Optional[TreeNode], depth: int):
            childSum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
            depth += 1
            if node.left:
                node.left.val = dSum[depth] - childSum
                dfs2(node.left, depth)
            if node.right:
                node.right.val = dSum[depth] - childSum
                dfs2(node.right, depth)
        dSum = []
        dfs1(root, 0)
        root.val = 0
        dfs2(root, 0)
        return root

Explore

在第一个DFS函数`dfs1`中，使用了递归的方式来遍历整棵树。函数接收当前节点以及节点的深度`depth`作为参数。每次访问一个新的深度层次时，首先检查`dSum`列表的长度是否等于当前的深度。如果等于，意味着这是该深度层次第一次被访问，因此在`dSum`列表中添加一个新的元素（初始值为0）。之后，无论树的形态如何（是否平衡），都能够保证每个节点的值都加到对应深度的总和中。这种方法通过递归确保了从根节点到每一个叶子节点的路径都被遍历，且每个节点根据其深度正确地贡献了值到`dSum`中。

在第二个DFS函数`dfs2`中，目的是将每个节点的值更新为所有堂兄弟节点值的总和。`dSum[depth]`在第一个DFS中已经计算了包含当前节点所有同级节点（包括其自身和所有堂兄弟节点）的值总和。为了得到仅堂兄弟节点的总和，需要从`dSum[depth]`中减去当前节点的直接子节点的值（因为子节点属于下一层，其值不应包括在当前层节点的计算中）。这样确保了更新的值是除去自身所有子节点的值后，该层其他节点的总和，即堂兄弟节点的总和。这种方法正确地实现了题目要求的功能，即每个节点值反映了所有堂兄弟节点的总和。

在题目中，堂兄弟节点定义为在同一深度但父节点不同的节点。根节点位于深度0，且在正常的二叉树中，根节点是唯一的，没有其他节点与其在同一深度上，因此它没有堂兄弟节点。因此，在`dfs2`函数开始时将根节点的值设置为0是合理的，因为按题目要求，它应该被其堂兄弟节点的总和替换，而它没有堂兄弟，所以和为0。这种设计准确地反映了题目的逻辑与要求。