Zenefits Interview - Determine If a Graph is a valid Binary Tree

INPUT: (A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)

 

OUTPUT: (A(B(D)(G))(C(E(F))(H)))

(parent(child)(child))

 

Error Code      Type of error

E1              More than 2 children

E2              Duplicate Edges - (A,B) (A,B)

E3              Cycle present

E4              Multiple roots

E5              Any other error   

 

就是给一个图，判断是不是合法的二叉树，是的话，输出二叉树的字符串表达式，不是的话，输出错误码。

 

public class GraphEdgeTree {

	public static class Edge {
		char from, to;
		public Edge(String exp) {
			String[] nodes = exp.replaceAll("[\\(\\)\\s]", "").split(",");
			from = nodes[0].charAt(0);
			to = nodes[1].charAt(0);
		}
	}
	
	private Map<Character, Character> map = new HashMap<>();
	private Map<Character, Set<Character>> childMap = new HashMap<>();
	private List<Edge> edges = new ArrayList<>();
	
	public GraphEdgeTree(String exp) {
		String[] arr = exp.split("\\s");
		for(String str:arr) {
			Edge edge = new Edge(str);
			edges.add(edge);
			map.put(edge.from, edge.from);
			map.put(edge.to, edge.to);
			
			Set<Character> children = childMap.get(edge.from);
			if(children == null) {
				children = new HashSet<Character>();
			}
			children.add(edge.to);
			childMap.put(edge.from, children);
		}
	}
	
	public Character find(char x) {
		Character parent = map.get(x);
		if(parent == null || parent == x) {
			return parent;
		}
		return find(parent);
	}
	
	public void union(char x, char y) {
		Character xp = find(x);
		Character yp = find(y);
		map.put(xp, yp);
	}
	
	public boolean isEdgeExisted(Edge edge) {
		Character p = map.get(edge.to);
		return p != null && p == edge.from;
	}
	
	public String buildTree() {
		for(Character key:childMap.keySet()) {
			Set<Character> set = childMap.get(key);
			if(set != null && set.size()>2) {
				return "E1";
			}
		}
		for(Edge edge:edges) {
			if(isEdgeExisted(edge)) {
				return "E2";
			}
			char xp = find(edge.from);
			char yp = find(edge.to);
			if(xp == yp) {
				return "E3";
			}
			union(edge.to, edge.from);
		}
		if(rootNum() > 1) {
			return "E4";
		}
		return null;
	}
	
	private int rootNum() {
		int cnt = 0;
		for(char key:map.keySet()) {
			if(find(key) == key) {
				cnt++;
			}
		}
		return cnt;
	}
	
	public String treeString(char root) {
		Set<Character> children = childMap.get(root);
		if(children == null || children.size() == 0) {
			return "("+root+")";
		}
		StringBuilder result = new StringBuilder("("+root);
		for(char child:children) {
			result.append(",").append(treeString(child));
		}
		result.append(")");
		return result.toString();
	}
	
	public char getRoot() {
		return find(edges.get(0).from);
	}
	
	public static void main(String[] args) {
		String input = "(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)";
		GraphEdgeTree gt = new GraphEdgeTree(input);
		String error = gt.buildTree();
		if(error != null) {
			System.out.println(error);
		} else {
			String result = gt.treeString(gt.getRoot());
			System.out.println(result);
		}
	}
}