623. 在二叉树中增加一行

https://leetcode-cn.com/problems/add-one-row-to-tree/

解法一：层序

import queue
class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        if not root:
            return root
        if d == 1:    #特殊情况
            newRoot = TreeNode(v)
            newRoot.left = root
            return newRoot
        q = queue.Queue()
        q.put(root)
        level = 1   #初始高度
        #层序遍历
        while q.qsize() > 0:
            count = q.qsize()
            for _ in range(count):
                node = q.get()
                if level == d-1:    #到达要插入的层
                    #创建新的左右子
                    newLeft, newRight = TreeNode(v), TreeNode(v)    
                    #左子插入
                    newLeft.left = node.left
                    node.left = newLeft
                    #右子插入
                    newRight.right = node.right
                    node.right = newRight
                if node.left:
                    q.put(node.left)
                if node.right:                  
                    q.put(node.right)
            if level == d-1:    #插入完成后直接返回，不用再访问下一层
                return root
            level += 1  #每层遍历完高度+1