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

Question

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

每个节点都有自己唯一的id。< code>parent_id在树中标识其父级。问题是如何对树进行前序遍历？(不一定是二叉树)

这是一个困扰我好几天的面试问题。我能想到的是使用哈希映射＜code＞映射

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);
}