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.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        

Solutions:
class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         if root:
             if d == 1:
                 new_root = TreeNode(v)
                 new_root.left = root
                 
                 return new_root 
 
             queue = [root]
             level = 1
             while queue and level < d:
                 row = []
                 for i in range(len(queue)):
                     node = queue.pop(0)
                     if level == d - 1:
                         row.append(node)
                     if node.left:
                         queue.append(node.left)
                     if node.right:
                         queue.append(node.right)
                 
                 level += 1
                                     
             for node in row:
                 old = node.left
                 node.left = TreeNode(v)
                 node.left.left = old
 
                 old = node.right
                 node.right = TreeNode(v)
                 node.right.right = old
         
         return root
             
             


class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         # if d == 1: # 广度搜索 64ms
         #     newroot = TreeNode(v)
         #     newroot.left = root
         #     return newroot
         # lastlevel = []
         # cur = 1
         # curlevel = [root]
         # nextlevel = []
         # while cur < d:
         #     for node in curlevel:
         #         if node:
         #             nextlevel.append(node.left)
         #             nextlevel.append(node.right)
         #     lastlevel = curlevel
         #     curlevel = nextlevel
         #     nextlevel = []
         #     cur += 1
         # count = 0
         # for node in lastlevel:
         #     if node:
         #         templeft, tempright = TreeNode(v), TreeNode(v)
         #         templeft.left = curlevel[count]
         #         tempright.right = curlevel[count+1]
         #         count += 2
         #         node.left = templeft
         #         node.right = tempright
         # return root
         
         if d == 1:
             newroot = TreeNode(v)
             newroot.left = root
             return newroot
         queue = [(root, 1)]
         for node, level in queue:
             if node.left:
                 queue.append((node.left, level+1))
             if node.right:
                 queue.append((node.right, level+1))
             if level == d-1:
                 newleft = TreeNode(v)
                 newleft.left = node.left
                 newright = TreeNode(v)
                 newright.right = node.right
                 node.left = newleft
                 node.right = newright
         return root

class Solution:
     
     def traverse_left(self, stack, node, node_depth, d):
         while node_depth + 1 < d and node.left is not None:
             stack.append((node.left, node_depth + 1))
             node = node.left
             node_depth += 1
     
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         
         if d == 1:
             new_root = TreeNode(v)
             new_root.left = root
             return new_root
         
         stack = [(root, 1)]
         self.traverse_left(stack, root, 1, d)
         
         while not (not stack):
             node, node_depth = stack.pop()
             if node_depth + 1 < d and node.right is not None:
                 stack.append((node.right, node_depth + 1))
                 self.traverse_left(stack, node.right, node_depth + 1, d)
               
             if node_depth == d - 1:
                 a = TreeNode(v)
                 a.left = node.left
                 node.left = a
                 b = TreeNode(v)
                 b.right = node.right
                 node.right = b
                 
         return root
         


# Definition for a binary tree node.
 # class TreeNode(object):
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         if d == 1:
             rt = TreeNode(v)
             rt.left = root
             return rt
         
         def DFS(rt, depth):
             if depth == d - 1:
                 newL = TreeNode(v)
                 newL.left = rt.left
                 newR = TreeNode(v)
                 newR.right = rt.right
                 rt.left = newL
                 rt.right = newR
                 return
             if rt.left:
                 DFS(rt.left, depth + 1)
             if rt.right:
                 DFS(rt.right, depth + 1)
         
         DFS(root, 1)
         return root
             
                 
     
             

class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         if not root:
             return
         if d == 1:
             new = TreeNode(v)
             new.left = root
             return new
         if d == 2:
             # Create new children.
             right, left = TreeNode(v), TreeNode(v)
 
             # Add roots children to these new children..
             right.right = root.right
             left.left = root.left
 
             # Set new children as roots children
             root.right, root.left = right, left
         else:
             self.addOneRow(root.right, v, d - 1)
             self.addOneRow(root.left, v, d - 1)
         return root


class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         if d == 1:
             nrt = TreeNode(v)
             nrt.left = root
             return nrt
         level = 1
         que = [root]
         d -= 1
         beg, end = 0, 1
         while beg < end:
             lev_cnt = 0
             i = beg
             if level == d:
                 while i < end:
                     p = que[i]
                     lt, rt = TreeNode(v), TreeNode(v)
                     lt.left = p.left
                     p.left = lt
                     rt.right = p.right
                     p.right = rt
                     i += 1
                 return root
             while i < end:
                 p = que[i]
                 if p.left:
                     que.append(p.left)
                     lev_cnt += 1
                 if p.right:
                     que.append(p.right)
                     lev_cnt += 1
                 i += 1
             beg = end
             end += lev_cnt
             level += 1
         return root
                 
                 
             
                 
                 


class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         q, depth = [root], 1
         while depth != d: parent, q, depth = q, [kid for node in q for kid in (node.left, node.right) if kid], depth+1
         if d != 1:
             for node in parent: node.left, node.right, node.left.left, node.right.right = TreeNode(v), TreeNode(v), node.left, node.right
             return root
         else: 
             first, first.left = TreeNode(v), root
             return first

class Solution:
     def addOneRow(self, root, v, d):
         """
         :type root: TreeNode
         :type v: int
         :type d: int
         :rtype: TreeNode
         """
         dummy, dummy.left = TreeNode(None), root
         row = [dummy]
         for _ in range(d - 1):
             row = [kid for node in row for kid in (node.left, node.right) if kid]
         for node in row:
             node.left, node.left.left = TreeNode(v), node.left
             node.right, node.right.right = TreeNode(v), node.right
         return dummy.left