面试被问到扁平数据结构转Tree这个问题怎么办？

面试被问到扁平数据结构转Tree这个问题怎么办 ？

哎呀，被问到扁平数据结构转Tree这个问题，这是面试官刁难你的高频问题之一啊。回答不好，面试官就会觉得你只是会递归的小学生，完全不值得高薪聘用啊！

不过别慌，跟着我念一遍这篇文章，你就能迅速懂得如何回答这个问题了。

常规方法

首先，我们要明确一个概念：扁平数据结构就是所有数据都在同一层级下，没有任何层级结构；而树形数据结构则是一种层级结构，具有一个根节点和多个子节点。所以，我们转换扁平数据结构为树形数据结构的关键在于识别每个节点的父子关系。

接下来，你可以对面试官大喊一声：“听好了，咳咳，我要开始讲思路了！” 那么，我们可以通过以下步骤将扁平数据结构转换为树形数据结构：

1. 创建一个空的根节点
2. 遍历所有节点，并根据其parentId找到对应的父节点
3. 将当前节点添加为父节点的子节点
4. 如果当前节点没有父节点，它将成为新的根节点

是不是非常简单啊！下面，我来展示一个JavaScript代码实现，假设我们有以下扁平数据结构：

[
  {id: 1, name: 'A', parentId: null},
  {id: 2, name: 'B', parentId: 1},
  {id: 3, name: 'C', parentId: 1},
  {id: 4, name: 'D', parentId: 2},
  {id: 5, name: 'E', parentId: 2},
  {id: 6, name: 'F', parentId: 3},
  {id: 7, name: 'G', parentId: 3},
  {id: 8, name: 'H', parentId: 4},
]

在这个例子中，我们可以看到每个节点都有一个唯一的id，一个名称和一个parentId，parentId是指它的父节点的id，如果没有父节点，parentId为null。让你看看你们这帮小学生的思路和我的有何不同。

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

  nodes.forEach(node => {
    map[node.id] = node
    node.children = []
  })

  nodes.forEach(node => {
    if (node.parentId) {
      map[node.parentId].children.push(node)
    } else {
      tree.push(node)
    }
  })

  return tree
}

看到这里，你不禁感慨，这代码写得真好！这不是小学生可以想到的，只有我这样的神仙才能想到啊！（滑稽）

不过，哪有这么简单的事呢？咳咳，这个代码还可以再优化哦！比如，我们可以减少循环次数，使用哈希表来存储节点，甚至还能使用并发机制来提高代码性能！

当然，如果你在面试的时候讲出了这些高级操作，面试官肯定会惊为天人，毫不犹豫地把 offer 递给你了。当然，如果面试官是我这种幽默的人，听完你的回答，估计会冒出一句：“哇，好厉害啊！可以详细讲讲怎么优化吗？”

减少循环次数

在之前的代码中，我们使用了两个forEach循环来遍历节点数组。但是，这会导致多次循环遍历同一个数组，从而降低性能。为了减少循环次数，我们可以使用单个for循环来遍历节点数组。

以下是修改后的代码：

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

  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i]
    map[node.id] = node
    node.children = []
    const parentId = node.parentId

    if (!parentId) {
      tree.push(node)
    } else {
      if (!map[parentId]) {
        map[parentId] = { id: parentId, children: [] }
      }
      map[parentId].children.push(node)
    }
  }

  return tree
}

我们将两个forEach循环替换为单个for循环。我们还添加了一个条件语句，以检查节点是否有父节点。如果没有父节点，我们将其添加到树的根节点中，否则我们将其添加到其父节点的children数组中。

使用哈希表

在之前的代码中，我们使用一个映射来存储节点。但是，对于较大的数据集，使用哈希表可以更快地查找节点。因此，我们可以使用JavaScript中的对象来代替映射。

以下是修改后的代码：

function buildTree(nodes) {
  const tree = {}
  const map = {}

  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i]
    map[node.id] = node
    node.children = []
    const parentId = node.parentId

    if (!parentId) {
      tree[node.id] = node
    } else {
      if (!map[parentId]) {
        map[parentId] = { id: parentId, children: [] }
      }
      map[parentId].children.push(node)
    }
  }

  return Object.values(tree)
}

我们将tree从数组改为对象，并使用node.id作为键。我们还将映射从Map对象改为普通对象。这样可以使代码更加简洁，并减少了一些额外的函数调用。

将数据进行排序

如果数据是按照id顺序排列的，可以使用二分查找来查找父节点，从而减少遍历的次数。因此，我们可以将节点数组按照id排序，以优化性能。

以下是修改后的代码：

function buildTree(nodes) {
  const tree = {}
  const map = {}
  nodes.sort((a, b) => a.id - b.id)

  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i]
    map[node.id] = node
    node.children = []
    const parentId = node.parentId

    if (!parentId) {
      tree[node.id] = node
    } else {
      const parentIndex = binarySearch(nodes, parentId)

      if (parentIndex !== -1) {
        const parentNode = nodes[parentIndex]

        if (!parentNode.children) {
          parentNode.children = []
        }

        parentNode.children.push(node)
      } else {
        if (!map[parentId]) {
          map[parentId] = { id: parentId, children: [] }
        }
        map[parentId].children.push(node)
      }
    }
  }

  return Object.values(tree)
}

function binarySearch(arr, id) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)
    const midId = arr[mid].id

    if (midId === id) {
      return mid
    } else if (midId < id) {
      start = mid + 1
    } else {
      end = mid - 1
    }
  }

  return -1
}

我们将节点数组按照id排序，并使用二分查找来查找父节点的索引。如果能够找到父节点，我们将当前节点添加到父节点的children数组中。否则，我们将当前节点添加到一个临时的映射中，并在之后的遍历中再次查找其父节点。这个版本的代码可以在数据集较大时更快地查找父节点。

避免重复遍历

如果同一个父节点有多个子节点，我们在找到该父节点之后，可以缓存其索引，以避免重复遍历。我们可以在map对象中添加一个__index属性，以存储该节点在节点数组中的索引。

以下是修改后的代码：

function buildTree(nodes) {
  const tree = {}
  const map = {}
  nodes.sort((a, b) => a.id - b.id)

  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i]
    map[node.id] = node
    node.children = []
    const parentId = node.parentId

    if (!parentId) {
      tree[node.id] = node
    } else {
      let parentIndex = map[parentId]?.__index

      if (parentIndex === undefined) {
        parentIndex = binarySearch(nodes, parentId)

        if (parentIndex !== -1) {
          map[parentId] = nodes[parentIndex]
          map[parentId].__index = parentIndex
        } else {
          if (!map[parentId]) {
            map[parentId] = { id: parentId, children: [] }
          }
        }
      }

      if (parentIndex !== undefined) {
        const parentNode = nodes[parentIndex]

        if (!parentNode.children) {
          parentNode.children = []
        }

        parentNode.children.push(node)
      } else {
        map[parentId].children.push(node)
      }
    }
  }

  return Object.values(tree)
}

function binarySearch(arr, id) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)
    const midId = arr[mid].id

    if (midId === id) {
      return mid
    } else if (midId < id) {
      start = mid + 1
    } else {
      end = mid - 1
    }
  }

  return -1
}

在这个版本中，我们将map对象中的映射改为使用缓存的索引值。在查找到父节点之前，我们首先尝试从map中获取该节点的__index属性。如果存在，则说明之前已经查找到该节点，我们可以直接使用缓存的索引值。否则，我们将使用二分查找来查找父节点，并缓存该节点的索引。这个版本的代码可以减少遍历次数，从而提高性能。

增加中间变量

我们可以增加一个中间变量来存储当前节点的父节点，从而避免多次查找父节点。这样可以使代码更加简洁，并减少额外的函数调用。

以下是修改后的代码：

function buildTree(nodes) {
  const tree = {}
  const map = {}
  nodes.sort((a, b) => a.id - b.id)

  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i]
    map[node.id] = node
    node.children = []
    const parentId = node.parentId
    let parent = null

    if (!parentId) {
      tree[node.id] = node
    } else {
      const parentIndex = map[parentId]?.__index

      if (parentIndex !== undefined) {
        parent = nodes[parentIndex]
      } else {
        parent = map[parentId] || { id: parentId, children: [] }
        map[parentId] = parent
      }

      if (!parent.children) {
        parent.children = []
      }

      parent.children.push(node)
    }

    node.__parent = parent
  }

  return Object.values(tree)
}

在这个版本中，我们添加了一个parent变量，用于存储当前节点的父节点。如果该节点已经在map中存在，则使用map中缓存的节点。否则，我们创建一个新的节点，并将其添加到map对象中。在添加子节点到父节点的children数组时，我们直接使用parent变量即可。最后，我们将parent赋值给节点的__parent属性。这个版本的代码可以使代码更加简洁，并减少额外的函数调用。

总结

目前为止，我已经介绍了对扁平数据结构转换为树形数据结构的代码进行优化的五个步骤。如果你有其他的优化思路，可以继续进行优化，比如利用 JavaScript 的并发机制来提高代码性能。但是，一般来说，上述的优化已经足够将代码性能提升到很高的水平。