Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's **original left subtree** should be the left subtree of the new left subtree root, its **original right subtree** should be the right subtree of the new right subtree root.

If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value **v** as the new root of the whole original tree, and the original tree is the new root's left subtree.

**Example 1:**

**Input:**
A binary tree as following:
4
/ \
2 6
/ \ /
3 1 5
**v = 1d = 2Output:**
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5

**Example 2:**

**Input:**
A binary tree as following:
4
/
2
/ \
3 1
**v = 1d = 3Output:**
4
/
2
/ \
1 1
/ \
3 1

**Note:**

The given d is in range [1, maximum depth of the given tree + 1].

The given binary tree has at least one tree node.

**Solution:**

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode addOneRow(TreeNode root, int v, int d) {
if(d==1)
{
TreeNode n = new TreeNode(v);
n.left=root;
return n;
}
insert(v,root,1,d);
return root;
}
public void insert(int val,TreeNode root,int depth,int d)
{
if(root==null) return;
if(depth==d-1)
{
TreeNode temp = root.left;
root.left = new TreeNode(val);
root.left.left = temp;
temp=root.right;
root.right = new TreeNode(val);
root.right.right=temp;
}
else
{
insert(val,root.left,depth+1,d);
insert(val,root.right,depth+1,d);
}
}
}
```

## Comments