Given the root of a tree, a value val and a positive integer depth, insert a complete row of new nodes with value val at that depth (the root is at depth 1). For every node p at depth depth - 1, create two new nodes valued val: the first becomes p's new left child and takes p's old left subtree as its left subtree; the second becomes p's new right child and takes p's old right subtree as its right subtree. If depth == 1, create a new root valued val whose left subtree is the whole original tree. Return the root.
Examples
4 4
/ \ / \
2 6 ==> 9 9
/ \ / / \
3 1 5 2 6
/ \ /
3 1 5
Input: root = build_tree([4, 2, 6, 3, 1, 5]), val = 9, depth = 2
Output: tree_to_list(...) == [4, 9, 9, 2, None, None, 6, 3, 1, 5]
Input: root = build_tree([4, 2]), val = 9, depth = 1
Output: [9, 4, None, 2]
Constraints
0 <= number of nodes <= 10001 <= depth <= (height of the tree) + 1
Goals
- Stop a level-order walk exactly one level above the insertion depth
- Attach old subtrees to the correct side of the new nodes