1030. Copy the Family Tree
A backup tool must clone a family tree so that later edits to the clone never touch the original. You are given root, the top ancestor of a tree in which each person may have any number of ordered children. Build and return the root of a completely new tree with the same shape, the same values and the same child order.
No node of the returned tree may be a node of the input tree. If root is null, return null. The tree can contain 100000 people in a single line, so do not recurse. Aim for O(n) time and O(n) space.
Example 1
- Input:
- root = [1,null,2,3,null,null,4]
- Output:
- [1,null,2,3,null,null,4]
- Explanation:
The copy has the same shape and values, but every person in it is a freshly created node.
Example 2
- Input:
- root = [5,null,6,9,null,7,8]
- Output:
- [5,null,6,9,null,7,8]
- Explanation:
Child order is preserved: 6 comes before 9, and 7 comes before 8 inside the branch of 6.
Constraints
0 ≤ number of nodes n ≤ 105
-104 ≤ node value ≤ 104
A node may have any number of children; the tree is given as a rooted N-ary tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)