623. 在二叉樹(shù)中增加一行

由于今日l(shuí)eetcode的每日一題是dota2黄选，擼狗表示不參與了~~

image-20201211142539498

思路

采用廣度優(yōu)先遍歷的方式称鳞，同時(shí)在遍歷的時(shí)候記錄當(dāng)前深度，如果深度與d相等嗜憔，那么就改變當(dāng)前層次樹(shù)的結(jié)構(gòu)挖滤，遍歷完了之后直接return root即可。

需要注意的點(diǎn)是，如果深度為1愈案，則可以直接創(chuàng)立一個(gè)新的節(jié)點(diǎn)，并把root賦值給樹(shù)的left節(jié)點(diǎn)即可鹅搪。（這是一個(gè)隱藏的坑站绪，用例可能因此跑不過(guò)）

需要注意的是，如示例1所示丽柿，插入節(jié)點(diǎn)后恢准，2變成了4的left的left，6變成了4的right的right甫题，這點(diǎn)需要注意一下馁筐。

# 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，則直接創(chuàng)立一個(gè)node坠非，并把root賦予給node.left并返回node
        if d == 1:
            node = TreeNode(v)
            node.left = root
            return node
        # 當(dāng)前深度為1
        current = 1
        deque = [root]
        # 否則開(kāi)始正常的bfs
        while len(deque) > 0:
            size = len(deque)
            for i in range(size):
                node = deque.pop(0)
                left = node.left
                right = node.right
                # 因?yàn)橐谏疃鹊纳弦粚舆M(jìn)行修改敏沉，所以是d-1
                if current == d-1:
                    node.left = TreeNode(v)
                    node.right = TreeNode(v)
                    node.left.left = left
                    node.right.right = right

                # 開(kāi)始正常的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

我們還可以優(yōu)化一下，因?yàn)樘砑油昴菍右院笱茁耄竺娴腷fs可以不繼續(xù)進(jìn)行了盟迟，當(dāng)后面的層數(shù)很深的時(shí)候，可以省下那些時(shí)間潦闲。

# 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攒菠，則直接創(chuàng)立一個(gè)node，并把root賦予給node.left并返回node
        if d == 1:
            node = TreeNode(v)
            node.left = root
            return node
        # 當(dāng)前深度為1
        current = 1
        queue = [root]
        # 否則開(kāi)始正常的bfs
        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                left = node.left
                right = node.right
                # 因?yàn)橐谏疃鹊纳弦粚舆M(jìn)行修改歉闰，所以是d-1
                if current == d-1:
                    node.left = TreeNode(v)
                    node.right = TreeNode(v)
                    node.left.left = left
                    node.right.right = right
                    # 添加完所有該層節(jié)點(diǎn)辖众，可以直接return root了，這里用break一樣
                    if i == size-1:
                        break
                # 否則開(kāi)始正常的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