623. Add One Row to Tree

Medium

30 Points

Tree

Depth-First Search

Breadth-First Search

Binary 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 depth. Note that the root node is at depth 1. The adding rule is:

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]

Example 2

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

Constraints

The number of nodes in the tree is in the range [1, 104].
The depth of the tree is in the range [1, 104].
-100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1