// 定義數(shù)組項(xiàng)的數(shù)據(jù)類型，包含id、name、parentId基本屬性
interface ArrayItem {
  id: number,
  name: string,
  parentId: number
}
// 定義樹節(jié)點(diǎn)的數(shù)據(jù)類型，包含id、name、可能存在的子節(jié)點(diǎn)
interface TreeNode {
  id: number,
  name: string,
  children?: TreeNode[], // 葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)
}
function array2Tree(arr: ArrayItem[]): TreeNode | null {
  // 用于id和TreeNode的映射，map<key, value>，可通過id快速查找到樹節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)
  const treeNode: Map<number, TreeNode> = new Map();
  let root = null; // 樹根節(jié)點(diǎn)
  arr.forEach(item => {
    const {id, name, parentId} = item; // 解構(gòu)賦值
    // 定義樹節(jié)點(diǎn)tree node，并使用Map維持id與節(jié)點(diǎn)之間的關(guān)系
    const node: TreeNode = {id, name}
    treeNode.set(id, node);
?
    // 使用parentId找出parentNode
    const parentNode = treeNode.get(parentId);
    if (parentNode) {
      if (parentNode.children == null) {
        parentNode.children = [];
      }
      // 找到父節(jié)點(diǎn)后，將當(dāng)前數(shù)組項(xiàng)轉(zhuǎn)換的節(jié)點(diǎn)添加到子節(jié)點(diǎn)列表中
      parentNode.children.push(node)
    }
?
    // 在第一次循環(huán)中找到根節(jié)點(diǎn)，我們假定id=0的表示根節(jié)點(diǎn)
    if (parentId === 0) {
      root = node;
    }
  })
  return root;
}
const tree = array2Tree(arrs); // 需要定義arrs
console.log(tree);

// 定義數(shù)據(jù)結(jié)構(gòu)
...
function tree2Array(root: TreeNode): ArrayItem[] {
  // 定義子節(jié)點(diǎn)和父節(jié)點(diǎn)的映射關(guān)系，map<子節(jié)點(diǎn)，父節(jié)點(diǎn)>
  const childToParent: Map<TreeNode, TreeNode> = new Map();

  const arr: ArrayItem[] = []; // 返回的數(shù)組

  // 廣度優(yōu)先遍歷樹，使用隊(duì)列保存節(jié)點(diǎn)
  const queue: TreeNode[] = [];
  queue.unshift(root); // 入隊(duì)，從頭部入隊(duì)
  while(queue.length) {
    const curNode = queue.pop(); // 出隊(duì)，從尾部出隊(duì)，保證先進(jìn)先出
    if (curNode == null) break; // 循環(huán)結(jié)束，使用==包括了null和undefined的情況

    const {id, name, children = []} = curNode; // 結(jié)構(gòu)賦值，葉子節(jié)點(diǎn)沒有children屬性，所以默認(rèn)為空數(shù)組

    const parentNode = childToParent.get(curNode); // 獲取當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
    const parentId = parentNode?.id || 0; // 獲取父節(jié)點(diǎn)id，根節(jié)點(diǎn)設(shè)置為0
    const item = {id, name, parentId}; // 定義數(shù)組項(xiàng)
    arr.push(item); // 插入到數(shù)組中

    // 繼續(xù)遍歷子節(jié)點(diǎn)，并且子節(jié)點(diǎn)入隊(duì)
    children.forEach(child => {
      // 如果有子節(jié)點(diǎn)，則把子節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)通過Map保持關(guān)系
      childToParent.set(child, curNode);

      // 入隊(duì)
      queue.unshift(child);
    })
  }

  return arr;
}
const array = tree2Array(obj); // 這個(gè)obj對(duì)象就是數(shù)組轉(zhuǎn)換為樹打印出的結(jié)果
console.log(array)