Add One Row to Tree

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth.

Note that the root node is at depth 1.

The adding rule is:

• Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
• cur's original left subtree should be the left subtree of the new left subtree root.
• cur's original right subtree should be the right subtree of the new right subtree root.
• If depth == 1, that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Examples

Example 1:

Input: root = [4, 2, 6, 3, 1, 5], val = 1, depth = 2

Output: [4, 1, 1, 2, null, null, 6, 3, 1, 5]

Explanation: At depth 1 we have node 4. We add new nodes with value 1 at depth 2. The original left subtree [2,3,1] becomes the left child of the new left node, and the original right subtree [6,5] becomes the right child of the new right node.

Example 2:

Input: root = [4, 2, null, 3, 1], val = 1, depth = 3

Output: [4, 2, null, 1, 1, 3, null, null, 1]

Explanation: At depth 2 we have node 2. We add new nodes with value 1 at depth 3.

Example 3:

Input: root = [1], val = 5, depth = 1

Output: [5, 1]

Explanation: Since depth is 1, we create a new root with value 5, and the original tree becomes its left subtree.

Constraints

• The number of nodes in the tree is in the range [1, 10⁴]
• The depth of the tree is in the range [1, 10⁴]
• -100 <= Node.val <= 100
• -10⁵ <= val <= 10⁵
• 1 <= depth <= the depth of tree + 1