1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import { TreeNode } from "../binary-tree-inorder-traversal/TreeNode.ts";
function lowestCommonAncestor(    root?: TreeNode | null,    p?: TreeNode | null,    q?: TreeNode | null,): TreeNode | null {    if (!root) return null;    const visited = new WeakSet<TreeNode>();
    const parent = new WeakMap<TreeNode, TreeNode | null>();    dfs(root, parent);
    while (p) {        visited.add(p);        p = parent.get(p);    }    while (q) {        if (visited.has(q)) return q;        q = parent.get(q);    }    return null;}function dfs(root: TreeNode, parent: WeakMap<TreeNode, TreeNode | null>) {    if (root.left) {        parent.set(root.left, root);        dfs(root.left, parent);    }    if (root.right) {        parent.set(root.right, root);        dfs(root.right, parent);    }}export default lowestCommonAncestor;