写出数据结构家谱问题数组和链表两种代码

数据结构的家谱问题通常涉及到构建一个表示层次结构的数据结构，例如树形结构，其中节点有父节点和子节点。这里我会分别给出数组（二叉树）和链表（单链表）实现这种家谱结构的简单示例。

**数组（二叉树）实现：**

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val);
        this.left = (left===undefined ? null : left);
        this.right = (right===undefined ? null : right);
    }
}

function createFamilyTree(parents: number[], children: number[][]): TreeNode[] {
    const tree = new Array(parents.length).fill(null);
    for (let i = 0; i < parents.length; i++) {
        tree[i] = new TreeNode(parents[i]);
        if (children[i].length > 0) {
            tree[i].left = createFamilyTree([], children[i]); // 递归处理左孩子
            tree[i].right = createFamilyTree([], children[i].slice(1)); // 递归处理右孩子
        }
    }
    return tree;
}

**链表（单链表）实现：**
由于链表每个节点只能有一个指向前驱和后继，我们需要额外的数据结构来存储父子关系。这可以借助哈希表来简化：

class Node {
    value: number;
    parent: Node | null;
    childList: Node[] = [];
    constructor(value?: number) {
        this.value = (value === undefined ? 0 : value);
    }
}

function buildLinkedList(familyMap: { [key: string]: string }): Node[] {
    const nodes = new Map();
    familyMap.forEach((child, parent) => {
        if (!nodes.has(parent)) {
            nodes.set(parent, new Node());
        }
        nodes.get(parent)?.childList.push(nodes.get(child));
    });
    return Array.from(nodes.values());
}