华为9.7笔试,第一题树节点,欢迎讨论不同方法,指出不足~
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
scanner.nextLine();
HashSet<Node> nodes = new HashSet<>();
HashSet<Node> father = new HashSet<>();
//为孩子节点确定父节点
for (int i = 0; i < m; i++) {
String[] tmp = scanner.nextLine().split(" ");
Node parent = new Node(Integer.parseInt(tmp[0]));
father.add(parent);
for (int j = 1; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j]);
Node child = new Node(k, parent);
nodes.add(child);
}
}
//如果父节点也为孩子节点,把父节点的父节点找到
t1:for (Node node2 :
father) {
for (Node node1 :
nodes) {
if (node1.parent != null && node2.val == node1.val) {
node2.parent = node1.parent;
continue t1;
}
}
//如果是根节点
nodes.add(node2);
}
int onePoint = scanner.nextInt();
int twoPoint = scanner.nextInt();
Node one = null, two = null;
//从所有节点找到连个目标点
for (Node node :
nodes) {
if (node.val == onePoint) {
one = node;
}
if (node.val == twoPoint) {
two = node;
}
}
//这里有没有简介一些的写法
//获取两个节点的父关系节点
ArrayList<Node> k1 = new ArrayList<>();
k1.add(one);
ArrayList<Node> k2 = new ArrayList<>();
k1.add(two);
ArrayList<Node> p1 = getParents(one.parent, k1);
ArrayList<Node> p2 = getParents(two.parent, k2);
//查看两个节点距离
int sum = 0;
for (Node node1 :
p1) {
sum++;
int tmp = 0;
for (Node node2 :
p2) {
tmp++;
if (node1.val == node2.val) {
sum += tmp;
System.out.println(sum - 1);
return;
}
}
}
System.out.println(-1);
}
public static ArrayList<Node> getParents(Node node, ArrayList<Node> arr) {
if (node == null)
return arr;
arr.add(node);
return getParents(node.parent, arr);
}
}
class Node {
Node parent;
final int val;
public Node(int val) {
this.val = val;
}
public Node(int val, Node parent) {
this.val = val;
this.parent = parent;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
if (val != node.val) return false;
return parent == null || parent.equals(node.parent);
}
@Override
public int hashCode() {
int result = parent == null ? 0 : parent.hashCode();
result = 31 * result + val;
return result;
}
} #华为笔试##华为机试##华为机考#

