1506. Find Root of N-Ary Tree

Use set

T: O(n)
S: O(n)

class Solution {
    public Node findRoot(List<Node> tree) {
        Set<Node> seen = new HashSet<>();
        for (Node node : tree) {
            for (Node next : node.children) {
                seen.add(next);
            }
        }

        Node root = null;
        for (Node node : tree) {
            if (!seen.contains(node)) {
                root = node;
                break;
            }
        }
        return root;
    }
}

Use sum

T: O(n)
S: O(1)

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};

[1,null,3,2,4,null,5,6]
       1
      324 

[1,null,
2,3,4,5,null,
null,6,7,null,
8,null,
9,10,null,
null,11,null,
12,null,
13,null,
null,14]
*/

class Solution {
    public Node findRoot(List<Node> tree) {
        int sum = 0;
        for (Node node : tree) {
            sum += node.val;
            for (Node next : node.children) {
                sum -= next.val;
            }
        }

        Node root = null;
        for (Node node : tree) {
            if (sum == node.val) {
                root = node;
                break;
            }
        }
        return root;
    }
}

/***
only root value wont delete by children value!

T: O(n)
S: O(1)

 */