每日一题20201211（623. 在二叉树中增加一行）

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