首页 > 试题广场 >

异或传递

[编程题]异或传递

热度指数：1124 时间限制：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)

枉做好人

//简单明了
public class Solution {
    private Map<Integer,TreeNode> map = new HashMap<Integer,TreeNode>();  
    //先序遍历，将树的id,节点记录下来，并重新赋值0
    public void Preorder(TreeNode root){
        if (root == null) return ;    
        map.put(root.val,root);
        root.val = 0;
        Preorder(root.left);
        Preorder(root.right);
    }
    //异或操作树
    public void SetTree(TreeNode root,int v){
        if (root == null) return;
            root.val ^= v;
        SetTree(root.left,v);
        SetTree(root.right,v);
    }
    public TreeNode xorTree (TreeNode root, ArrayList<ArrayList<Integer>> op) {
        Preorder(root);
        for (int i =0; i < op.size(); i++){
            SetTree(map.get(op.get(i).get(0)),op.get(i).get(1));
        }
        return root;
    }
}

发表于 2022-08-03 15:06:22 回复(0)

loveling

由于异或操作结果与先后顺序无关，所以可以先求对某个节点执行所有操作后的结果，然后dfs将值传递至子树上的节点。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回值的树节点中val表示节点权值
     * @param root TreeNode类 给定的初始树节点中的val表示节点编号
     * @param op int整型vector<vector<>> op的组成为[[id,v],[id,v],[id,v],...]
     * @return TreeNode类
     */
    TreeNode* xorTree(TreeNode* root, vector<vector<int> >& op) {
        // write code here
        unordered_map<int, int> m;
        for(auto& v:op)
        m[v[0]]^=v[1];
        search(root,m, 0);
        return root;
    }
    
    void search(TreeNode* t,unordered_map<int, int>& m, int n)
    {
        if(t==nullptr)
            return;
        t->val = m[t->val];
        t->val^=n;
        search(t->left,m,t->val);
        search(t->right,m,t->val);
    }
};

发表于 2022-06-15 18:16:14 回复(0)

霸王龙v2

import java.util.*;

public class Solution {
    public TreeNode xorTree (TreeNode root, ArrayList<ArrayList<Integer>> op) {
        Map<Integer, Integer> map = new HashMap<>();
        for (List<Integer> l : op) {
            map.put(l.get(0), map.getOrDefault(l.get(0), 0) ^ l.get(1));
        }
        search(root, map, 0);
        return root;
    }
    
    private static void search(TreeNode root, Map<Integer, Integer> map, int n) {
        if (root == null) return;
        root.val = map.getOrDefault(root.val, 0);
        root.val ^= n;
        search(root.left, map, root.val);
        search(root.right, map, root.val);
    }
}

发表于 2022-07-17 13:24:26 回复(0)

程序员十年

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回值的树节点中val表示节点权值
     * @param root TreeNode类 给定的初始树节点中的val表示节点编号
     * @param op int整型vector<vector<>> op的组成为[[id,v],[id,v],[id,v],...]
     * @return TreeNode类
     */
    unordered_map<int, TreeNode*> m;    // 通过编号映射到树的节点，后面通过编号找树的对应节点的时候会便捷点
    
    // 先序遍历，将树的编号id映射到所对应的节点，用map记录下来这段关系，并将节点的值重新赋值为0，因为题目要求每个节点的权值为0
    void Preorder(TreeNode* root) {
        if(root == nullptr) return;
        m[root->val] = root;
        root->val = 0;
        Preorder(root->left);
        Preorder(root->right);
    }
    
    // 从根节点开始，把根节点下面的整棵树的节点值都异或一遍
    void SetTree(TreeNode* root, int v) {
        if(root == nullptr)    return;
        root->val ^= v;
        SetTree(root->left, v);
        SetTree(root->right, v);
    }
    
    TreeNode* xorTree(TreeNode* root, vector<vector<int> >& op) {
        Preorder(root);
        for(int i = 0; i < op.size(); ++i) {
            auto t = m[op[i][0]];
            SetTree(t, op[i][1]);
        }
        return root;
    }
    
    //另外一种思路：但是行不通的，看看就行
    // for循环：深度优先遍历，在遍历的时候，如果val和op[i][0]相等，就让m[root]^=op[i][1]
    // 不过这样的话，虽然能够让每个节点的权值都进行异或，但是返回的值不是一棵完整的树(题目要return TreeNode*类型)，是一个map，如果还另外去构建一棵树的话，就过于麻烦了
    // 也就是说题目暗含的意思就是要你把节点的val改掉，改成0^op[i][1]，而不是上面你那个意思。
};

发表于 2022-10-15 15:01:12 回复(0)

小学二年级了

先通过对每一根节点进行懒标记，因为异或的顺序不会对结果产生影响所以只要在最后赋值的时候把懒标记下推就好

最后赋值的过程直接完全调用懒标记就可以因为mii本身也为全0并不会影响值

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回值的树节点中val表示节点权值
     * @param root TreeNode类 给定的初始树节点中的val表示节点编号
     * @param op int整型vector<vector<>> op的组成为[[id,v],[id,v],[id,v],...]
     * @return TreeNode类
     */
    void fzTree(TreeNode* root, unordered_map<int, int> &lay, int val, int id) {
        if (root -> val == id) {
            lay[root -> val] ^= val;
            return;
        }
        
        if(root -> left != NULL) {
            fzTree(root -> left, lay, val, id);
        } 
            
        if(root -> right != NULL) {
            fzTree(root -> right, lay, val, id);
        }
    }
    
    void buildTree(TreeNode* root, TreeNode* fhs, unordered_map<int, int> &mii, unordered_map<int, int> &lay) {
        if(root -> left != NULL) {
            lay[root -> left -> val] ^= lay[root -> val];
            TreeNode* left = (TreeNode*) malloc(sizeof(TreeNode));
            left -> left = NULL;
            left -> right = NULL; 
            left -> val = mii[root -> left -> val] ^ lay[root -> left -> val];
            fhs -> left = left ;
            
            buildTree(root -> left, fhs -> left, mii, lay);
        } 
            
        if(root -> right != NULL) {
            lay[root -> right -> val] ^= lay[root -> val];
            TreeNode* right = (TreeNode*) malloc(sizeof(TreeNode));
            right -> left = NULL;
            right -> right = NULL;
            right -> val = mii[root -> right -> val] ^ lay[root -> right -> val];
            fhs -> right = right ;
            buildTree(root -> right, fhs -> right, mii, lay);
        }
    }
    
    TreeNode* xorTree(TreeNode* root, vector<vector<int> >& op) {
        //无用的mii
        unordered_map<int, int> mii{};
        //树的异或值懒标记
        unordered_map<int, int> lay{};
        // write code here

        //懒标记赋值过程
        for (auto i : op) {
            // i[0]是id i[1]是v
            lay[i[0]] ^= i[1];
        }
        
        //返回树
        TreeNode* fhs = (TreeNode*) malloc(sizeof(TreeNode));
        fhs -> val = mii[root -> val] ^ lay[root -> val];
        fhs -> left = NULL;
        fhs -> right = NULL;
        TreeNode* build = root;
        buildTree(build, fhs, mii, lay);
        
        return fhs;
    }
};

发表于 2022-08-24 15:21:09 回复(0)

打水漂

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回值的树节点中val表示节点权值
     * @param root TreeNode类 给定的初始树节点中的val表示节点编号
     * @param op int整型ArrayList<ArrayList<>> op的组成为[[id,v],[id,v],[id,v],...]
     * @return TreeNode类
     */
    public TreeNode xorTree (TreeNode root, ArrayList<ArrayList<Integer>> op) {
        // write code here
        int sum = 1;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            TreeNode front = q.poll();
            //System.out.println(front.val);
            if(front.left != null) {q.add(front.left); sum++;}
            if(front.right != null) {q.add(front.right); sum++;}
        }
        int[]&nbs***bsp;= new int[sum + 1];
        for(int i = 0; i < op.size(); i++) {
            int idx = op.get(i).get(0);
            int val = op.get(i).get(1);
            or[idx] ^= val;
        }
        dfs(root,&nbs***bsp;0);
        return root;
    }
    private void dfs(TreeNode root, int[]&nbs***bsp;int val) {
        if(root == null) return;
        root.val = val ^ or[root.val];
        if(root.left != null) dfs(root.left,&nbs***bsp;root.val);
        if(root.right != null) dfs(root.right,&nbs***bsp;root.val);
    }
}

发表于 2022-08-14 16:10:10 回复(0)

苏觅云

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回值的树节点中val表示节点权值
     * @param root TreeNode类 给定的初始树节点中的val表示节点编号
     * @param op int整型vector<vector<>> op的组成为[[id,v],[id,v],[id,v],...]
     * @return TreeNode类
     */
    TreeNode *xorTree(TreeNode *root, vector<vector<int> > &op) {
        // write code here
        unordered_map<int, int> mp;
        for (auto &opi : op) {
            mp[opi[0]] ^= opi[1];
        }
        dfs(root, mp, 0);
        return root;
    }

    void dfs(TreeNode *root, unordered_map<int, int> &mp, int pre) {
        if (root == nullptr) return;
        pre = root->val = mp[root->val] ^ pre;
        dfs(root->left, mp, pre);
        dfs(root->right, mp, pre);
    }
};

发表于 2022-08-01 14:53:26 回复(0)