题解 | #异或传递#

牛客不保存代码，记录一下。

常规的暴力解法：

1. 处理op数组，将[[3,2],[1,4],[1,3],[4,2],[2,1]]中[1,4],[1,3]这种情况合并为[1,7]，这里合不合并都一样，是性能的问题。
2. 遍历，将每个节点的值设置为0，同时用map<int, TreeNode*>保存节点的编号，map的好处就是通过节点标号找之前的地址比较方便（这里的遍历顺序无所谓，用了层序遍历是复习一下，用其他遍历代码会更少，处理起来也更优雅）
3. 逐个处理op数组

class Solution {
public:
	void travel(TreeNode* root, int value) {
		if (root == nullptr)
			return;
		root->val ^= value;
		travel(root->left, value);
		travel(root->right, value);
	}
  
	TreeNode* xorTree(TreeNode* root, vector<vector<int> >& op) {
		if (root == nullptr)
			return root;
      
		//part1: 合并op数组
      	map<int, int> mp;		//[节点编号,亦或的值]
		for (auto vec : op)
			mp[vec[0]] = (mp[vec[0]] ^ vec[1]);
      
		//part2: 层序遍历处理树节点
      	queue<TreeNode*> que;
		que.push(root);
		map<int, TreeNode*> tree;//[节点编号,节点的指针]
		while (!que.empty()) {
			int size = que.size();
			for (int i = 0; i < size; ++i) {
				TreeNode* node = que.front();
				tree[node->val] = node;
				node->val = 0;
				que.pop();
				if (node->left) que.push(node->left);
				if (node->right) que.push(node->right);
			}
		}
      
      	//part3: 遍历op数组，处理每个节点及其子树
		for (auto m : mp) {
			// m.first; 代表节点编号， m.second;代表亦或的值
			travel(tree[m.first], m.second);
		}
		return root;
	}
};