# 2445. Number of Nodes With Value One
###### tags: `Leetcode` `Medium` `Tree` `DFS`
Link: https://leetcode.com/problems/number-of-nodes-with-value-one/description/
## 思路
跟sweep line的感觉有点像
所有的变化都先记下来 最后经过一遍遍历 apply这些变化 得到答案
只不过现在我们把遍历换成了dfs
## Code

class Solution {
    public int numberOfNodes(int n, int[] queries) {
        int[] arr = new int[n];
        for(int q:queries){
            arr[q-1] ^= 1;
        }
        return dfs(arr, 0);
    }
    public int dfs(int[] arr, int curr){
        int ans = arr[curr];
        if(curr*2+1<arr.length){
            arr[curr*2+1] ^= arr[curr];
            ans += dfs(arr, curr*2+1);
        }
        if(curr*2+2<arr.length){
            arr[curr*2+2] ^= arr[curr];
            ans += dfs(arr, curr*2+2);
        }
        return ans;
    }
}