热乎乎的狗家电面

暴雪私生子777 发表于 2018-11-25 06:46
第二道题目别的面试里面也有，请问是leetcode题目吗

思路可以类似于lowest common ancestor吧

这个题因为不知道root 所以我感觉要先向上找a的ancestor， check 这个node是否也是b的ancestor（a/b反过来也一样）
check这一步也是dfs 所以写了两个dfs的function
一个用来找所有的ancestor
一个用来check
不知道思路对不对 求指点~求加米~

1. class Node {
   
2.         Node father;
   
3.         Node mother;
   
4.         List<Node> children;
   
5.         public Node() {
   
6.         father = new Node();
   
7.         mother = new Node();
   
8.         children = new LinkedList<>();
   
9. }
   
10. }
    
11. 
    
12. boolean res = false;
    
13. Set<Node> set = new HashSet<>();
    
14. public boolean areRelative(Node a, Node b) {
    
15.         getAncestor(a, b);
    
16.         return res;
    
17. }
    
18. 
    
19. private void getAncestor(Node a, Node b) {
    
20.         if (a == null) return;
    
21.         if (res) return;
    
22.         dfs(a, b);
    
23.         getAncestor(a.mother, b);
    
24.         getAncestor(a.father, b);
    
25.         return;
    
26. }
    
27. // check all the ancestors of a
    
28. // if one of them is ancestor of b, then they are relative
    
29. private void dfs(Node a, Node b) {
    
30.         if (res) return;
    
31.         if (a == null || b == null) return;
    
32.         if (set.contains(a)) return;
    
33.        
    
34.         if (a == b) {
    
35.         res = true;
    
36.         return;
    
37. }
    
38. 
    
39. for (Node n : a.children) {
    
40.         dfs(n, b);
    
41. }
    
42. return;
    
43. }
    

复制代码