623. Add One Row to Tree [Medium

623. Add One Row to Tree

很简单，用队列，宽度优先遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def addOneRow(self, root, v, d):
        """
        :type root: TreeNode
        :type v: int
        :type d: int
        :rtype: TreeNode
        """
        if d < 1:
            return False
        if d == 1:
            node = TreeNode(v)
            node.left = root
            return node
        cnt = 0
        qu = [root]
        while d != cnt:
            cnt += 1
            if cnt == d - 1:
                for i in range(len(qu)):
                    node = qu.pop(0)
                    new_l = TreeNode(v)
                    new_r = TreeNode(v)
                    if node.left:
                        new_l.left = node.left
                    if node.right:
                        new_r.right = node.right
                    node.left = new_l
                    node.right = new_r
            else:
                for i in range(len(qu)):
                    node = qu.pop(0)
                    if node.left:
                        qu.append(node.left)
                    if node.right:
                        qu.append(node.right)
        return root