G家面经求指导

给出一个迭代器，迭代器里存了很多个类R的实例, 类R里只有两个参数，都是String类型，分别代表Parent 和 Child，child只有一个Parent，Parent 可以有任意数量child
按所给示例输出所有的层级关系

eg：
A
  B1.1point3acres缃�
  B2
    C1
    C2
  B3
    D1
    D2
在面经里看到说用tree+哈希表，还是不太明白，有会写的仔细说一下思路吧。

题目的要求其实就是”给定树中每一条边，打印这棵树”。

所谓“tree+哈希表”的意思是先在内存中用指针（或引用）的连接方式把这棵树表示出来。为此需要写一个类
class StringTreeNode {
  String str;
  StringTreeNode parent;
  ArrayList<StringTreeNode> children;
  ...
}
每遍历R中的一条边，就检查Parent和Child所代表的StringTreeNode是否都已经被创建过了，如果有任一者未创建的话则先创建之，然后把二者连接在一起。检查的方法则是通过查询一个HashMap<String, StringTreeNode>来完成，该HashMap中存放的是“目前为止已经遇到过的String”。

树建立好以后，从root开始DFS就能够打印出树的内容。对于有Parent节点的树来说，找root应该不难。

不过，这道题的题目并没有说所有的R一定只形成一棵树，所以有可能会存在多个root。这种情况要先跟面试官沟通清楚。

stellari 发表于 2016-2-11 11:50
题目的要求其实就是”给定树中每一条边，打印这棵树”。

所谓“tree+哈希表”的意思是先在内存中用指针 ...

不用建立树的，虽然树比较直观，但是其实你只要HashMap<String, ArrayList<String>> 就可以表示出来树的关系了；
原因是： 这个跟treenode不太一样，每个node content就只有一个string变量，换句话说两个不同的treenode不能有相同的string；
所以给了任何一个node，用hashmap查一下就知道他的children都有啥了，不用tree里面的pointer （不好意思我主要用c+＋）