首页 > 试题广场 >

异或传递

[编程题]异或传递

小红有一棵 $\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}

。

算法知识视频讲解

直角三角熊

发表于 2023-03-19 13:53:58

牛客不保存代码，记录一下。常规的暴力解法：处理op数组，将[[3,2],[1,4],[1,3],[4,2],[2,1]]中[1,4],[1,3]这种情况合并为[1,7]，这里合不合并都一样，是性能的问题。遍历，将每个节点的值设置为0，同时用map<int, TreeNode*>保展开全文

上传者：小小

难度：

8条回答 43收藏 1879浏览

异或传递

扫一扫，把题目装进口袋