data-structures - 给定父节点数组，打印出树的前序遍历

Question

给定一个未排序的节点数组，其中节点定义为：
Node { int id; int parent_id; string label; }

每个节点都有自己唯一的 id。parent_id在树中识别其父项。问题是如何对树进行前序遍历？（不一定是二叉树）

这是一个困扰我好几天的面试题。我能想到的是使用一个哈希映射map<int,list<node> >，其中 key 是 parentid。那我就不能更进一步了。我应该从地图构建树并进行前序遍历，还是有直接从地图中进行的好方法？那怎么办？任何提示表示赞赏！

Answer 1

所以你需要：

map<int, list<Node> > childMap;
map<int, Node> nodeMap;

你会发现一个没有父节点（parent_id = -1 或其他）的节点，这显然是根节点。在设置上面的地图后，您可以为该节点调用以下函数。

preOrder(int id)
{
  process(nodeMap[id]);
  foreach (Node node: childMap[id])
    preOrder(node);
}