題目描述：
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 = 1
d = 2
Output:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
Example 2:
Input:
A binary tree as following:
4
/
2
/ \
3 1
v = 1
d = 3
Output:
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.
一刷題解（Recursion）：
這題要我們在一個二叉樹中的某一層(d)，插入一層值為(v)的節點，然後將原來下一層的左子節點變成插進來的這一層的左子節點，右子節點也一樣。
雖然這題標為Medium，但是解題思路很簡單，一看就知道可以用DFS來做。直接利用遞歸，從樹的頂部向其左右子節點移動，並記錄當前層數深度。當深度等於插入目標層數 – 1時，代表當前節點的下一層就是要插入的層數。
因此，我們在當前層停下來，先聲明一個TreeNode保在當前層子節點的引用，以免丟失，然後把當前節點的子節點指向以插入值進行初始化的節點（new TreeNode(addVal))，最後再把剛剛保存下來的舊子節點變成插入節點的子節點（node.left.left = currNext），完成。
public class Solution {
public TreeNode AddOneRow(TreeNode root, int v, int d) {
//Add in first stair
if(d == 1)
{
TreeNode newHead = new TreeNode(v);
newHead.left = root;
return newHead;
}
RowAdder(root, v, d, 1);
return root;
}
void RowAdder(TreeNode node, int addVal, int targetStair, int currDepth)
{
if(node == null) { return; }
//if currDepth = targetStair - 1
//means next stair should be new Node(addVal);
if(currDepth == targetStair - 1)
{
//Insert addVal Node between currNode and currNode.next
//Save curr next node first;
TreeNode currNext = node.left;
//Add addVal in next node
node.left = new TreeNode(addVal);
//Set next Node(addVal)'s next node be currNext
node.left.left = currNext;
//So be it in RightSide
currNext = node.right;
node.right = new TreeNode(addVal);
node.right.right = currNext;
}
else
{
//DFS
RowAdder(node.left, addVal, targetStair, currDepth + 1);
RowAdder(node.right, addVal, targetStair, currDepth + 1);
}
}
}