Given an N-ary tree as a list of nodes Node[] tree. Each node has a unique value:
class Node {
int val;
List<Node> children = new ArrayList<>();
Node(int val) {
this.val = val;
}
}Find and return its root.
public Node findRoot(Node[] tree) {
}Example 1:
1
/ | \
2 3 4
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
n1.children.add(n2);
n1.children.add(n3);
n1.children.add(n4);
Input: [n2, n3, n1, n4]
Output: n1Follow-up
Can you do it using O(1) space?
Solution
To achive O(1) space we can use the same idea as here https://leetcode.com/problems/single-number
Each node will be visited twice during iteration (1st time in the list and 2nd time as a child of another node) expect the root. So find the sum of the vals of all nodes, then subtract all the children's vals, and finally the result will be the id of the root. Use it to find the corresponding node in the list. To avoid overflow xor all the vals instead.
Java: https://leetcode.com/playground/NRQ9CQ4K
Time complexity: O(n).
Space complexity: O(1).
Comments (8)