以下是 LeetCode 1938 “查询最大基因差” 的 JavaScript 实现，核心思路与 Java 版本一致：离线查询 + 可回溯 Trie。

解题思路

1. 建树：根据 parents 数组构建邻接表，并找到根节点（parent = -1）
2. 离线分组：将所有查询按 node 分组，DFS 遍历到该节点时一并处理
3. 可回溯 Trie：
   · 进入节点时 insert(node)，离开时 remove(node)
   · 保证 Trie 中始终保持当前节点到根路径上的所有值
4. 查询最大异或：在 Trie 中贪心地走与 val 的当前位相反的路径

JavaScript 代码

```javascript
class TrieNode {
    constructor() {
        this.children = [null, null];  // [0, 1]
        this.count = 0;               // 经过该节点的数量
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(num) {
        let node = this.root;
        for (let i = 17; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!node.children[bit]) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
            node.count++;
        }
    }

    remove(num) {
        let node = this.root;
        for (let i = 17; i >= 0; i--) {
            const bit = (num >> i) & 1;
            node = node.children[bit];
            node.count--;
        }
    }

    maxXor(val) {
        let node = this.root;
        let result = 0;
        for (let i = 17; i >= 0; i--) {
            const bit = (val >> i) & 1;
            const opposite = bit ^ 1;
            if (node.children[opposite] && node.children[opposite].count > 0) {
                result |= (1 << i);
                node = node.children[opposite];
            } else {
                node = node.children[bit];
            }
        }
        return result;
    }
}

var maxGeneticDifference = function(parents, queries) {
    const n = parents.length;

    // 1. 构建树
    const tree = Array.from({ length: n }, () => []);
    let root = -1;
    for (let i = 0; i < n; i++) {
        if (parents[i] === -1) {
            root = i;
        } else {
            tree[parents[i]].push(i);
        }
    }

    // 2. 离线查询分组
    const nodeQueries = Array.from({ length: n }, () => []);
    queries.forEach(([node, val], idx) => {
        nodeQueries[node].push([val, idx]);
    });

    // 3. DFS + 回溯 Trie
    const result = new Array(queries.length);
    const trie = new Trie();

    function dfs(node) {
        // 进入节点：插入当前节点值
        trie.insert(node);

        // 处理该节点上的所有查询
        for (const [val, idx] of nodeQueries[node]) {
            result[idx] = trie.maxXor(val);
        }

        // 递归子节点
        for (const child of tree[node]) {
            dfs(child);
        }

        // 离开节点：删除当前节点值
        trie.remove(node);
    }

    dfs(root);
    return result;
};
```

复杂度分析

· 时间复杂度：O((n + q) * 18)，每个节点的插入/删除以及每个查询都需要 18 次位操作（2^17 = 131072 > 10^5）
· 空间复杂度：O(n * 18 + q)，Trie 最大节点数和查询数组的大小

关键代码说明

部分 说明
TrieNode 包含 children[2]（0/1子节点）和 count（经过次数）
insert(num) 逐位插入，count++
remove(num) 逐位 count--，不删除节点本身
maxXor(val) 贪心走相反位，若不存在则走相同位
dfs(node) 进入时 insert，处理查询，递归子树，离开时 remove

示例运行

```javascript
console.log(maxGeneticDifference(
    [-1, 0, 1, 1],
    [[0, 2], [3, 2], [2, 5]]
));
// 输出: [2, 3, 7]
```

要点总结

1. 离线查询：按节点分组，DFS 时一次性处理同一节点的所有查询，避免重复遍历
2. 可回溯 Trie：使用计数而非真正删除节点，支持快速回溯
3. 位运算优化：Trie 深度固定为 18，覆盖数据范围 10^5
4. DFS 顺序：先插入当前节点 → 处理查询 → 递归子节点 → 回溯删除，保证路径正确性