值为 1 的节点数

Submission

运行时间: 124 ms

内存: 28.0 MB

class Solution:
    def numberOfNodes(self, n: int, queries: List[int]) -> int:
        flip=[0]*(n+1) 
        for q in queries:
            flip[q]^=1
        for i in range(2,n+1):
            flip[i]^=flip[i//2]
        
       
        return sum(flip)

Explain

题解采用了翻转操作的方法来计算值为1的节点数。初始化一个列表 flip，其长度为 n+1，所有元素初始值为0，用来记录每个位置的翻转状态。遍历输入的 queries，每遇到一个元素，就将对应 flip 中的位置进行异或操作（0变1，1变0），表示翻转状态。然后从索引2开始，利用父节点的翻转状态影响到当前节点，即每个节点的最终状态由它自身的翻转以及它的父节点的翻转状态决定。最后，统计 flip 列表中值为1的元素数量，即为最终的结果。

时间复杂度: O(q + n)

空间复杂度: O(n)

class Solution:
    def numberOfNodes(self, n: int, queries: List[int]) -> int:
        flip=[0]*(n+1)  # 初始化 flip 数组，长度为 n+1，用来记录每个位置的翻转状态
        for q in queries:
            flip[q]^=1  # 对于每个 query，翻转相应位置的值
        for i in range(2,n+1):
            flip[i]^=flip[i//2]  # 父节点的翻转状态影响到当前节点
        return sum(flip)  # 返回 flip 中值为1的数量，即为结果

Explore

在二叉树结构中，索引1是根节点，它没有父节点。从索引2开始遍历是因为2是二叉树中第一个有父节点的子节点（索引2的父节点是索引1）。因此，从索引2开始可以确保每个遍历到的节点都有一个有效的父节点索引可参考，即 i/2。这样可以正确地应用父节点的翻转状态到当前节点。

每个节点的翻转状态是由其自身的翻转和其直接父节点的翻转状态决定的，这是通过递归的逻辑实现的。当考虑节点i的翻转状态时，其已经包含了其父节点i/2的翻转状态，而父节点i/2的翻转状态又包含了其父节点(i/2)/2的翻转状态，依此类推。因此，通过每个节点只考虑其直接父节点的翻转状态，间接地考虑了所有祖先节点的翻转状态。

算法实现中并没有直接处理索引超出n的情况，这通常依赖于输入的约束和外部校验来确保。在实际应用中，应当在函数调用前验证所有的queries中的索引都不超过n。如果需要在算法内部处理，可以在修改flip数组之前添加一个检查条件，确保q的值不大于n。

使用异或操作是因为它能简洁地实现状态切换（从0到1或从1到0），而不需要额外的条件判断。每次异或1都会反转当前状态。使用加法或布尔数组切换也可以实现相同功能，但加法会引入额外的复杂度，例如需要额外的操作来限制值的范围（防止超过1）。布尔数组切换（例如，通过not操作）也是一个有效的方法，但在语言处理位操作时，异或可能在性能上更优。