华为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; } }
#华为笔试##华为机试##华为机考#