# 1506. Find Root of N-Ary Tree
###### tags: `Leetcode` `Bit Manipulation` `Medium` `Tree` `XOR`
Link: https://leetcode.com/problems/find-root-of-n-ary-tree/
## 思路
### 思路一 $O(N)$ $O(1)$
我们把数组里的每个节点和每个节点的所有子节点都访问一次，我们会发现只有根节点被访问了一次，其余的节点都访问了两次（作为数组的节点元素访问一次，作为子节点访问一次）。

显然，我们只要在上述的遍历过程中，把所有的val都亦或起来，得到的就是根节点的val值。再扫一遍就可以根据val把根节点挑出来。
### 思路二 $O(N)$ $O(N)$
把所有节点的child节点都加进set里面 再遍历一次所有节点 没有在set里面的val就是root
## Code
### 思路一 $O(N)$ $O(1)$

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        rootVal = 0
        for node in tree:
            rootVal ^= node.val
            for child in node.children:
                rootVal ^=child.val

        for node in tree:
            if node.val == rootVal:
                return node

class Solution {
    public Node findRoot(List<Node> tree) {
        int rootVal = 0;
        for(Node n:tree){
            rootVal ^= n.val;
            for(Node c:n.children){
                rootVal ^= c.val;
            }
        }
        
        for(Node n:tree){
            if(n.val==rootVal) return n;
        }
        return null;
    }
}

### 思路二 $O(N)$ $O(N)$

class Solution {
    public Node findRoot(List<Node> tree) {
        Set<Integer> set = new HashSet<>();
        for(Node n:tree){
            for(Node c:n.children){
                set.add(c.val);
            }
        }
        for(Node n:tree){
            if(!set.contains(n.val)) return n;
        }
        return null;
    }
}