给一个Employee类，有一个String name和一个List<Employee> directReport来表示一个公司的组织结构，然后给定一个公司的ceo和两个员工的名字，找到这两个员工的第一个common manager，给的两个员工一定存在。N-try tree的first common ancestor。楼主就用最naive的方法先找到从根到target节点的path然后在两个path中找第一个common ancestor。在电脑上写代码和测试样例，改掉测试样例的一个小bug之后通过。要求优化，说了用postorder traversal的方法来找，这样只需要遍历树一遍，说了一下整体的过程没有coding。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class Solution {
public static class Employee {
List<Employee> employees;
String name;
int num;
public Employee(String name) {
this.name = name;
this.employees = new ArrayList<>();
}
}
private void outputTree(List<String> input) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}
updateNum(head);
print(head, "");
}
private void print(Employee emp, String prefix) {
System.out.println(prefix + "" + emp.name + " " + emp.num);
StringBuilder sb = new StringBuilder();
for (char c : prefix.toCharArray()) {
if (c == '\\') {
sb.append(' ');
} else if (c != '_' && c != '-') {
sb.append(c);
}
}
for (int i = 0; i < emp.employees.size(); i++) {
Employee emp2 = emp.employees.get(i);
if (i != emp.employees.size() - 1) {
print(emp2, sb.toString() + "|-");
} else {
print(emp2, sb.toString() + "\\_");
}
}
}
private int updateNum(Employee emp) {
int res = emp.num;
for (Employee emp2 : emp.employees) {
res += updateNum(emp2);
}
emp.num = res;
return res;
}
public String getCommon(List<String> input, String name1, String name2) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}
Employee common = getCommon(head, map.get(name1), map.get(name2));
return common.name;
}
private Employee getCommon(Employee root, Employee emp1, Employee emp2) {
if (root == emp1 || root == null || root == emp2) {
return root;
}
Employee find1 = null;
Employee find2 = null;
for (Employee child : root.employees) {
Employee find = getCommon(child, emp1, emp2);
if (find != null) {
if (find1 == null) {
find1 = find;
} else if (find2 == null) {
find2 = find;
}
}
}
if (find1 != null && find2 != null) {
return root;
} else {
return find1;
}
}
public static void main(String args[]) {
Solution s = new Solution();
List<String> list = Arrays.asList("Bob,Alice,3", "Carol,Bob,2",
"Richard,Carol,5", "Kim,Richard,5", "Tom,Carol,5",
"David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1", "Alice,,5",
"Chen,Eve,5", "Cen,Eve,2", "Eli,Cen,1", "Baba,Cen,2",
"Rui,Chen,2");
// List<String> list = Arrays.asList("Bob,Alice,3", "Alice,,5",
// "Cal,Alice,3");
// List<String> list = Arrays.asList("Alice,,5", "Bob,Alice,3",
// "Carol,Bob,2", "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1");
s.outputTree(list);
System.out.println(s.getCommon(list, "Alice", "Tom"));
}
}
