2641.二叉树的堂兄弟节点II

链接：2641.二叉树的堂兄弟节点II
难度：Medium
标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树
简介：给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有堂兄弟节点值的和。如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为堂兄弟。请你返回修改值之后，树的根 root 。

题解 1 - python

编辑时间：2024-02-07
执行用时：41ms
内存消耗：16.5MB
编程语言：python
解法介绍：bfs时当记录完一层的节点后进行遍历处理。

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        root.val = 0
        map = {}
        q = deque()
        q.append(root)
        size = 1
        sum = 0
        while q:
            node = q.popleft()
            if node.left:
                map[node.left] = node
                q.append(node.left)
                sum += node.left.val
            if node.right: 
                map[node.right] = node
                q.append(node.right)
                sum += node.right.val
            size -= 1
            if size == 0:
                nums = []
                for child in q:
                    csum = 0
                    if map[child].left: csum += map[child].left.val
                    if map[child].right: csum += map[child].right.val
                    nums.append(sum - csum)
                for i in range(len(q)):
                    q[i].val = nums[i]
                sum = 0
                size = len(q)
        return root

题解 1 - python​

题解 1 - python