关系型数组转换成树形结构对象

var obj = [
    { id:3, parent:2 },
    { id:1, parent:null },
    { id:2, parent:1 }
]
转换成
o = { 
  id: 1, 
  parent: null, 
  children: [{ 
    id: 2, 
    parent: 1, 
    children: [{ 
      id: 3, 
      parent: 2 
    }] 
  }]
};

首次解题

我看到题目时，果断想到了用递归法去实现

function buildTree(data, parentId = null) {
  const tree = {};
  data
    .filter(item => item.parent === parentId)
    .forEach(item => {
      tree.id = item.id;
      tree.parent = item.parent;
      const children = buildTree(data, item.id);
      if (children.length) {
        tree.children = children;
      }
    });
  return tree;
}

const obj = [
  { id: 3, parent: 2 },
  { id: 1, parent: null },
  { id: 2, parent: 1 },
];

const result = buildTree(obj);
console.log(result);

后面我心想面试官应该不会考得这么简单，莫不是还得看看时间复杂度？

tip

算了算该函数的时间复杂度为O(n^2)，其中n为数据数组的长度。

原因是在该函数中，对数据数组进行了多次遍历和递归操作。具体来说，在每次递归调用时，都需要对数据数组进行一次过滤操作，时间复杂度为O(n)，然后又需要对过滤后的数组进行一次遍历操作，时间复杂度同样为O(n)。因此，总的时间复杂度为O(n^2)。

如果数据数组的长度很大，该函数的效率可能较低。可以考虑优化算法，例如使用哈希表等数据结构，可以将时间复杂度降至O(n)。

caution

补充：

时间复杂度怎么算

时间复杂度是用来衡量算法执行时间随输入规模增加而增加的增长率，通常使用大O符号表示。

要计算时间复杂度，通常需要分析算法的执行步骤数量，然后根据执行步骤数量的增长规律得出时间复杂度。在分析执行步骤数量时，常见的操作包括循环、递归、条件分支、函数调用等。

例如，在一个循环中执行n次操作的算法，时间复杂度可以表示为O(n)；在一个嵌套循环中执行n^2次操作的算法，时间复杂度可以表示为O(n^2)；在一个递归调用中，每次递归的输入规模为n-1，总共递归了n次的算法，时间复杂度可以表示为O(n)。

通常情况下，时间复杂度较低的算法更优，因为它们可以在更短的时间内处理更大规模的输入数据。

优化解题

这种方法的时间复杂度为 O(n)，比前一种方法更优秀，因为它只需要遍历输入数据两次，而且不需要递归。

function buildTree(data) {
  const dict = {};
  data.forEach(item => {
    dict[item.id] = { id: item.id, parent: item.parent, children: [] };
  });
  const root = dict[null];
  data.forEach(item => {
    if (item.parent !== null) {
      dict[item.parent].children.push(dict[item.id]);
    }
  });
  return root.children[0];
}

const obj = [
  { id: 3, parent: 2 },
  { id: 1, parent: null },
  { id: 2, parent: 1 },
];

const result = buildTree(obj);
console.log(result);

为了实现更好的性能，可以使用对象字典（Object Dictionary）来避免每次在数组中进行查找和筛选操作。在对象字典中，我们将每个节点的 id 作为 key，对应的节点对象作为 value，这样可以通过 O(1) 的时间复杂度快速查找节点。

tip

对象字典补充:

对象字典（Object Dictionary）是一种数据结构，它使用对象的属性作为键，对应的对象作为值，以实现高效的数据查找和访问。在示例代码中，我们使用对象字典来实现对树节点的快速访问和操作。

具体来说，我们将每个节点的 id 作为 key，对应的节点对象作为 value 存储在字典中。这样，在需要访问某个节点时，我们可以直接使用该节点的 id 作为 key，通过 O(1) 的时间复杂度快速查找到对应的节点对象。

使用对象字典可以在许多场景中提高性能，比如在构建树结构时，可以使用对象字典来避免每次在数组中进行查找和筛选操作。另外，在 JavaScript 中，对象字典可以通过对象字面量或 Map 对象来实现。对象字面量是一种简单的字典实现，而 Map 对象则是一种更为强大的字典实现，支持任意类型的键和值，并提供了更多的 API 方法。

关系型数组转换成树形结构对象

首次解题​

优化解题​

首次解题

优化解题