623. 在二叉树中增加一行
由于今日leetcode的每日一题是dota2，撸狗表示不参与了~~
image-20201211142539498
思路
采用广度优先遍历的方式，同时在遍历的时候记录当前深度，如果深度与d相等，那么就改变当前层次树的结构，遍历完了之后直接return root即可。
需要注意的点是，如果深度为1，则可以直接创立一个新的节点，并把root赋值给树的left节点即可。（这是一个隐藏的坑，用例可能因此跑不过）
需要注意的是，如示例1所示，插入节点后，2变成了4的left的left，6变成了4的right的right，这点需要注意一下。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
# 如果d是1，则直接创立一个node，并把root赋予给node.left并返回node
if d == 1:
node = TreeNode(v)
node.left = root
return node
# 当前深度为1
current = 1
deque = [root]
# 否则开始正常的bfs
while len(deque) > 0:
size = len(deque)
for i in range(size):
node = deque.pop(0)
left = node.left
right = node.right
# 因为要在深度的上一层进行修改，所以是d-1
if current == d-1:
node.left = TreeNode(v)
node.right = TreeNode(v)
node.left.left = left
node.right.right = right
# 开始正常的bfs
if node.left is not None:
deque.append(node.left)
if node.right is not None:
deque.append(node.right)
current += 1
return root
image-20201211144017079
我们还可以优化一下，因为添加完那层以后，后面的bfs可以不继续进行了，当后面的层数很深的时候，可以省下那些时间。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
# 如果d是1，则直接创立一个node，并把root赋予给node.left并返回node
if d == 1:
node = TreeNode(v)
node.left = root
return node
# 当前深度为1
current = 1
queue = [root]
# 否则开始正常的bfs
while len(queue) > 0:
size = len(queue)
for i in range(size):
node = queue.pop(0)
left = node.left
right = node.right
# 因为要在深度的上一层进行修改，所以是d-1
if current == d-1:
node.left = TreeNode(v)
node.right = TreeNode(v)
node.left.left = left
node.right.right = right
# 添加完所有该层节点，可以直接return root了，这里用break一样
if i == size-1:
break
# 否则开始正常的bfs
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
current += 1
return root
