将平铺数组转为树状结构

面试了十几个高级前端，竟然连（扁平数据结构转Tree）都写不出来 - 掘金

递归调用实现

时间复杂度 O(n^2) ，空间复杂度：O(n^2) 缺点： 不适合大规模数据

const nodes = [
  { id: 1, name: "Node 1", parentId: null },
  { id: 2, name: "Node 2", parentId: 1 },
  { id: 3, name: "Node 3", parentId: 1 },
  { id: 4, name: "Node 4", parentId: 2 },
  { id: 5, name: "Node 5", parentId: 2 },
  { id: 6, name: "Node 6", parentId: null },
];

// 定义一个函数，用于将数组转换为树状结构
function arrayToTree(array, parentId = null) {
  const tree = [];
  // 如果当前节点的父节点ID等于给定的父节点ID
  array.forEach((item) => {
    if (item.parentId === parentId) {
      // 递归查找当前节点的子节点,并将子节点添加到当前节点的children属性中
      // 这里是递归调用，构建子树 将子树赋值给当前节点的 children 属性
      item.children = arrayToTree(array, item.id);
      // 将当前节点添加到树中
      tree.push(item);
    }
  });
  return tree;
}

//      1      6  
//    2   3
//  4  5 

const res = arrayToTree(nodes);
console.log(res);

递归调用简化版本 filter+map

注意有性能问题

const arrayToTree = (nodes, parentId = null) => {
  return nodes
    .filter((node) => node.parentId === parentId)
    .map((node) => ({
      ...node,
      children: arrayToTree(nodes, node.id),
    }));
};
const tree = arrayToTree(nodes, null);
console.log(tree);
// 1. 使用 filter 方法筛选出所有具有指定父节点 ID 的节点。
// 2. 使用 map 方法对筛选出的节点进行处理。
// 3. 对于每个节点，递归调用 arrayToTree 函数来构建其子树。
// 4. 注意map箭头函数返回一个对象需要加 =>（{}）括号

使用循环（哈希映射）

时间复杂度：O(n)，其中 n 是节点的数量。 空间复杂度：O(n) 适合大规模数据

const arrayToTree = (array) => {
  const map = {};
  const tree = [];

  // 1. 创建map映射
  array.forEach((item) => {
    // 构建一个map对象，key为节点id，值为原对象每个加上children属性
    map[item.id] = { ...item, children: [] };
  });
  // map结果如上图

  // 2. 遍历节点数组
  array.forEach((item) => {
    if (item.parentId !== null) {
      // 如果当前节点有父节点，将其添加到父节点的子节点数组中
      map[item.parentId].children.push(map[item.id]);
    } else {
// 否则，将其作为根节点添加到最终的树结构中
      tree.push(map[item.id]);
    }
  });

  return tree;
};

const res = arrayToTree(array);
console.log(res);

for of简化一点点

function arrayToTreeLoop(nodes) {
  const map = {};
  const tree = [];

  for (const node of nodes) {
    map[node.id] = { ...node, children: [] };
  }

  // Object.values获取对象的所有属性值，返回数组
  for (const node of Object.values(map)) {
    if (node.parentId === null) {
      tree.push(node);
    } else {
      map[node.parentId].children.push(node);
    }
  }

  return tree;
}

const tree = arrayToTreeLoop(nodes);

使用reduce

function arrayToTreeReduce(nodes) {
  // 1. 构建map结构，注意这步的map构建不能放在reduce中写
  const map = {};
  for (const node of nodes) {
    map[node.id] = { ...node, children: [] };
  }

  // 2. reduce遍历，其实和前面一样的
  const tree = nodes.reduce((acc, node) => {
    // map[node.id] = { ...node, children: [] };
    // 这里写map会有问题，Error
    // 如果颠倒pid顺序 map未构建出来，children取不到报错
    if (node.parentId === null) {
      acc.push(map[node.id]);
    } else {
      map[node.parentId].children.push(map[node.id]);
    }

    return acc;
  }, []);

  return tree;
}

const tree = arrayToTreeReduce(nodes);

console.log(tree);

//  颠倒顺序是指：
const nodes = [
  { id: 1, name: "Node 1", parentId: null },
  // id为4，pid2放在前面，这时候map还未完全构建好
  { id: 4, name: "Node 4", parentId: 2 },
  { id: 2, name: "Node 2", parentId: 1 },
  { id: 3, name: "Node 3", parentId: 1 },
  { id: 5, name: "Node 5", parentId: 2 },
  { id: 6, name: "Node 6", parentId: null },
];

哈希表 new Map 最优解！！

时间复杂度：O(n)，其中 n 是节点的数量。 空间复杂度：O(n)。 适合大规模数据，而且由于使用了 Map，能够更方便地进行节点的查找和删除。

const map = new Map([
  ['name', '张三'],
  ['title', 'Author']
]);
// 新建map对象，成员是双元素数组

function arrayToTreeMap(nodes) {
  // 将数组转为map对象
  const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
  const tree = [];

  // map.values（）返回键值
  // map.get(key) 读取key对应的键值
  for (const node of map.values()) {
    if (node.parentId === null) {
      tree.push(node);
    } else {
      map.get(node.parentId).children.push(node);
    }
  }
  return tree;
}

const tree = arrayToTreeMap(nodes);

使用深度优先搜索

时间复杂度：O(n)，其中 n 是节点的数量。 空间复杂度：O(n)。 优缺点：相比于方法二、方法三和方法四，可以更方便地进行深度优先搜索。

function arrayToTreeDFS(nodes) {
  const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
  const tree = [];
  for (const node of map.values()) {
    if (node.parentId === null) {
      dfs(node, tree);
    }
  }
  function dfs(node, parent) {
    if (parent) {
      parent.children.push(node);
    }
    for (const child of node.children) {
      dfs(map.get(child.id), node);
    }
  }
  return tree;
}
const tree = arrayToTreeDFS(nodes);

使用深度优先搜索（DFS）的方式来实现数组转换为树的方法。它基于递归地遍历树的节点，将每个节点添加到其父节点的 children 数组中。 下面是简要说明：

1. 首先，通过 nodes.map() 方法创建一个 Map 对象，其中键是节点的 id，值是节点对象，包括 children 属性，初始为空数组。
2. 然后，遍历 Map 中的每个节点对象。对于每个节点，如果它是树的根节点（即 parentId 为 null），则调用 dfs() 函数进行深度优先搜索。
3. 在 dfs() 函数中，将当前节点添加到其父节点的 children 数组中，并递归调用 dfs() 函数处理当前节点的子节点。
4. 最后，返回树结构。

这种实现方式利用了深度优先搜索的特性，在遍历树的过程中直接进行了节点的组织，从而构建出树状结构。 如果nodes 数组是事先按照节点的父子关系顺序排列的，那么这种方式会是一个非常高效的方法。

树形结构扁平化

要将树形结构扁平化，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历树的节点，并将每个节点添加到一个数组中。

深度优先搜索（DFS）

function treeToArray(tree) {
  let res = []
  for (const item of tree) {
    // 使用解构将children属性剔除
    const { children, ...i } = item
    if (children && children.length) {
      // 递归调用
      res = res.concat(treeToArray(children))
    }
    res.push(i)
  }
  return res
}

1. 定义了一个 treeToArray 函数，它接受一个树形结构作为参数，并返回一个数组。
2. 使用 for...of 循环遍历树中的每个节点。
3. 对于每个节点，使用解构赋值将其 children 属性剔除，因为我们只需要节点本身的数据，而不需要子节点的信息。
4. 如果当前节点有子节点（即 children 存在且不为空数组），则递归调用 treeToArray 函数来处理子节点，并将结果与当前节点的数据合并。
5. 将处理后的当前节点数据添加到结果数组中。
6. 最后返回结果数组。

reduce实现，简洁一点

function treeToArray(tree) {
  return tree.reduce((res, item) => {
    const { children, ...i } = item
    return res.concat(i, children && children.length ? treeToArray(children) : [])
  }, [])
}

广度优先搜索（BFS）

我们使用一个队列来按层级顺序迭代树的节点。对于每个节点，我们首先将其从队列中取出并添加到结果数组中，然后将其子节点依次添加到队列中。

function flattenTreeBFS(tree) {
    const flattened = [];
    const queue = [...tree];

    while (queue.length > 0) {
        const node = queue.shift();
        // 剔除当前节点的 children 属性，只保留节点数据
        const { children, ...data } = node; 
        // 将节点数据添加到结果数组中
        flattened.push(data);
        if (children && children.length) {
            queue.push(...children); // 将子节点依次添加到队列末尾中
        }
    }

    return flattened;
}

// 当然用栈结构也可以实现

按照层级顺序依次处理每个节点及其子节点。 在每次循环迭代中，我们从队列中取出一个节点，将其数据（不包含子节点）添加到结果数组中。然后，如果当前节点有子节点，就将子节点依次添加到队列末尾。这样，通过不断地从队列中取出节点并处理，直到队列为空，我们就完成了树形结构的扁平化。

// 使用哈希表 最优解！
const arrayToTree = (array) => {
  const tree = [];
  // 将原数组转为map对象，key为id，value为对象
  const map = new Map(
    array.map((item) => [item.id, { ...item, children: [] }])
  );

  for (const item of map.values()) {
    // 根节点
    if (item.parentId === null) {
      tree.push(item);
    } else {
      map.get(item.parentId).children.push(item);
    }
  }
  return tree;
};