LC: 1506. Find Root of N Ary Tree
https://leetcode.com/problems/find-root-of-n-ary-tree/
1506. Find Root of N-Ary Tree
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
Nodeobject into an array in an arbitrary order.The driver code will pass the array to
findRoot, and your function should find and return the rootNodeobject in the array.The driver code will take the returned
Nodeobject and serialize it. If the serialized value and the input data are the same, the test passes.
Example 1:
Example 2:
Constraints:
The total number of nodes is between
[1, 5 * 104].Each node has a unique value.
Follow up:
Could you solve this problem in constant space complexity with a linear time algorithm?
The Essence:
Die Werte der Knoten treten jeweils einmal auf.
Details:
It will be translated soon.
Unique value in an array of values can be found using the XOR operation. For each node in the nodes list, we XOR their value to some number (initially 0), then XOR their children's value to that number. Nodes that are node will be XORed twice to that number, which is equivalent to turning on and turning off the effect of their bit values on that number. Only node's value's bits will stay the same. Then simply the node with this remaining value needs to be found.
Solution(s) and Further Explanation:
Default Code:
Last updated