497. Insert a Floor
An architect models a building as a binary tree whose top node root is on floor 1, its children on floor 2, and so on. She wants to add a whole new floor of rooms, each with value v, so that the new floor becomes floor number depth.
If depth is 1, create a new root with value v and make the old tree its left subtree. Otherwise, for every node on floor depth - 1, create two nodes with value v: the new left child takes over the old left subtree as its own left subtree, and the new right child takes over the old right subtree as its own right subtree. Return the root of the resulting tree.
Example 1
- Input:
- root = [4,2,6,3,1,5], v = 7, depth = 2
- Output:
- [4,7,7,2,null,null,6,3,1,5]
- Explanation:
With depth 2 the new floor of 7s sits directly below the root, and the old left and right subtrees hang from the new left and right 7 respectively.
Example 2
- Input:
- root = [4,2,null,3,1], v = 5, depth = 4
- Output:
- [4,2,null,3,1,5,5,5,5]
- Explanation:
The tree has 3 levels, so depth 4 adds a floor of 5s under the nodes 3 and 1, two new 5s under each.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val, v ≤ 1000
1 ≤ depth ≤ (number of levels of the tree) + 1. An empty tree has 0 levels.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)