This was asked in LinkedIn Interview Given a list of child->parent relationships, build a binary tree out of it. All the element Ids inside the tree are unique. Example: Given the following relationships: Child Parent IsLeft 15 20 true 19 80 true 17 20 false 16 80 false 80 50 false 50 null false 20 50 true You should return the following tree: 50 / 20 80 / \ / 15 17 19 16 Function Signature /** * Represents a pair relation between one parent node and one child node inside a binary tree * If the _parent is null, it represents the ROOT node */ class Relation { int parent; int child; bool isLeft; }; /** * Represents a single Node inside a binary tree */ class Node { int id; Node * left; Node * right; } /** * Implement a method to build a tree from a list of parent-child relationships * And return the root Node of the tree */ Node * buildTree (vector<Relation> & data) { }
public class GenerateBinaryTree {
public static class Relation {
public Integer parent, child;
public boolean isLeft;
public Relation(Integer parent, Integer child, boolean isLeft) {
this.parent = parent;
this.child = child;
this.isLeft = isLeft;
}
}
public static class Node {
public Integer val;
public Node left, right;
public Node(Integer val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
private static HashMap<Integer, Node> mapOfNodes;
public static Node buildTree(List<Relation> relations) {
mapOfNodes = new HashMap<Integer, Node>();
Iterator<Relation> relationsIterator = relations.iterator();
Relation relation;
Node root = null;
while (relationsIterator.hasNext()) {
Node parentNode, childNode;
relation = relationsIterator.next();
if (relation.parent == null) {
root = getChildNode(relation.child);
continue;
}
if (mapOfNodes.containsKey((relation.parent))) {
parentNode = mapOfNodes.get(relation.parent);
childNode = getChildNode(relation.child);
if (relation.isLeft)
parentNode.left = childNode;
else
parentNode.right = childNode;
} else {
childNode = getChildNode(relation.child);
parentNode = new Node(relation.parent, relation.isLeft ? childNode : null, relation.isLeft ? null : childNode);
mapOfNodes.put(relation.parent, parentNode);
}
}
return root;
}
private static Node getChildNode(Integer child) {
Node childNode;
if (mapOfNodes.containsKey((child))) {
childNode = mapOfNodes.get(child);
} else {
childNode = new Node(child, null, null);
mapOfNodes.put(child, childNode);
}
return childNode;
}
}
Generate a binary tree from parent->child relationship
原文：http://www.cnblogs.com/apanda009/p/7944902.html