题目描述
You are given all the nodes of an N-ary tree as an array of Node
objects, where each node has a unique value.
Return the root of the N-ary tree.
Custom testing:
An N-ary tree can be serialized as represented in its level order traversal where each group of children is separated by the null
value (see examples).
For example, the above tree is serialized as [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]
.
The testing will be done in the following way:
- The input data should be provided as a serialization of the tree.
- The driver code will construct the tree from the serialized input data and put each
Node
object into an array in an arbitrary order. - The driver code will pass the array to
findRoot
, and your function should find and return the rootNode
object in the array. - The driver code will take the returned
Node
object and serialize it. If the serialized value and the input data are the same, the test passes.
Example 1:
Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.
Example 2:
Input: tree = [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]
Output: [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]
Constraints:
- The total number of nodes is between
[1, 5 * 104]
. - Each node has a unique value.
思路
- 直观做法:用HashSet存储每个节点的children,然后因为root不可能在children这个Set中,所以我们可以用O(N)时间和空间找到根节点root.
- O(1)做法:异或思想,因为两个相同数作XOR,结果是0,那么我们在处理每个节点时,可以将节点本身和它的children节点的值作异或运算,即每次计算 =
current_node.val ^ ALL(current_node.children.val)
. 这样我们可以发现,只有根节点root被计算了一次,其余节点(root的children们)都会被计算两次(第一次是作为children跟root一块计算了,第二次是遍历到自己节点时计算自己的值)最后,异或的数值结果就是root.val,因为其余的node.val都被异或了2次,结果总和为0.
代码
/*
// 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;
}
};
*/
class Solution {
public Node findRoot(List<Node> tree) {
if (tree == null || tree.size() == 0)
return null;
int sum1 = 0;
for (Node node : tree) {
sum1 ^= node.val;
for (Node child : node.children) {
sum1 ^= child.val;
}
}
for (Node node : tree) {
if (sum1 == node.val)
return node;
}
return null;
}
}