腾讯音乐4.27笔试第二题

第二题A不出来啊，改了好久也只有20%，有大佬看看么。。

class TreeNode:
    def __init__(self, x=0,left=None,right=None):
        self.val = x
        self.left = left
        self.right = right

def xorTree(root: TreeNode, op) -> TreeNode:
    def xorT(startNode,v):
             '''
             从当前节点开始，对该节点及其所有子节点进行异或
             '''
        if startNode == None:
            return
            
                #如果是初次修改就用0异或，并把结果保存在val中，如果不是就直接用val异或
        if not visit[startNode][1]:
            startNode.val = 0 ^ v
        else:
            startNode.val = startNode.val ^ v
        
        visit[startNode][1] = True#已经访问过
        
        startNode.left = xorT(startNode.left,v)
        startNode.right = xorT(startNode.right,v)
        return startNode

    def doOneOp(Node,code,v):
             '''
             完成一次操作
             '''
        if Node == None:
            return

        if visit[Node][0] == code:
            Node = xorT(Node,v)
            return
        else:
            doOneOp(Node.left, code, v)
            doOneOp(Node.right, code, v)
    
    def initVisit(root,visit):
             '''
             初始化visit，第一个元素记录位置信息（编号）,第二个元素记录是否是初次修改
             '''
        if root == None:
            return
        visit[root] = [root.val,False]
        initVisit(root.left,visit)
        initVisit(root.right,visit)
        
    visit = {}#创建一个哈希表，第一个元素记录位置信息（编号）,第二个元素记录是否是初次修改
    initVisit(root,visit)
    for opt in op:
        doOneOp(root,opt[0],opt[1])

    return root

#腾讯音乐娱乐笔试#

全部评论

推荐最新楼层

哈密瓜123

西安交通大学 C++

from collections import deque class Solution: def xorTree(self, root: TreeNode, op: List[List[int]]) -> TreeNode: hashdict = self.cengxu(root) for idx, number in op: node = hashdict[idx] self.singlexor(node, number) return root def singlexor(self, node, number): if not node: return node.val = node.val ^ number self.singlexor(node.left, number) self.singlexor(node.right, number) return def cengxu(self, root): deq = deque([root]) ans = {} while deq: size = len(deq) path = {} for _ in range(size): node = deq.popleft() path[node.val] = node node.val = 0 if node.left: deq.append(node.left) if node.right: deq.append(node.right) ans.update(path) return ans

腾讯音乐4.27笔试第二题

全站热榜