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

// 定義數據結構
...
function tree2Array(root: TreeNode): ArrayItem[] {
  // 定義子節(jié)點和父節(jié)點的映射關系，map<子節(jié)點，父節(jié)點>
  const childToParent: Map<TreeNode, TreeNode> = new Map();

  const arr: ArrayItem[] = []; // 返回的數組

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

    const {id, name, children = []} = curNode; // 結構賦值，葉子節(jié)點沒有children屬性，所以默認為空數組

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

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

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

  return arr;
}
const array = tree2Array(obj); // 這個obj對象就是數組轉換為樹打印出的結果
console.log(array)