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
