异或传递

[编程题]异或传递

热度指数：1025 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红有一棵 $\mathit n$ 个节点的二叉树，节点的编号为 $1\sim n$ ，且每个节点的初始权值都为 $0$ 。

对于这棵二叉树小红会进行 $k$ 次操作，每次操作小红会选择一个节点编号 $id$ ，让以该编号节点为根的子树上节点的权值都异或上 $v$ 。

小红现在给你这棵树的结构以及每次操作的情况，小红想知道在她进行 $k$ 次操作之后该棵二叉树各个节点的权值情况是多少呢，请你返回该树的权值情况。

你需要完善一个函数，函数的第一个参数为给定的树的编号情况，第二个参数代表小红的操作，每个操作的第一项为编号 $id$ ，第二项为异或的值 $v$ 。

示例1

输入

{1,2,3},[[2,4],[1,2]]

输出

{2,6,2}

说明

  1    权值情况：    0  ->   0  ->  2
 / \               / \     / \    / \    
2   3             0   0   4   0  6   2

示例2

输入

{2,1,3,#,4},[[3,2],[1,4],[1,3],[4,2],[2,1]]

输出

{1,6,3,#,4}

备注:

。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

臆想者

from collections import defaultdict
class Solution:
    def xorTree(self , root: TreeNode, op: List[List[int]]) -> TreeNode:
        qu = []
        op_dict = defaultdict(list)
        index2nums = defaultdict(int)
        for i in op:
            op_dict[i[0]].append(i[1])
        qu.append(root)
        while qu:
            node = qu.pop(0)
            index = node.val
            if node.left!=None:
                qu.append(node.left)
            if node.right!=None:
                qu.append(node.right)
            if index in op_dict:
                for i in op_dict[index]:
                    temp = []
                    temp.append(node)
                    while temp:
                        temp_node = temp.pop(0)
                        index = temp_node.val
                        index2nums[index]= index2nums[index]^i
                        if temp_node.left!=None:
                            temp.append(temp_node.left)
                        if temp_node.right!=None:
                            temp.append(temp_node.right)
        qu.append(root)
        while qu:
            node = qu.pop(0)
            node.val = index2nums[node.val]
            if node.left!=None:
                qu.append(node.left)
            if node.right!=None:
                qu.append(node.right)
        return root

发表于 2022-07-24 16:48:52 回复(0)