每日一题20201211(623. 在二叉树中增加一行)

标签:修改   sel   行修改   one   problems   示例   +=   时间   turn   

623. 在二叉树中增加一行

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

每日一题20201211(623. 在二叉树中增加一行)

标签:修改   sel   行修改   one   problems   示例   +=   时间   turn   

原文地址:https://www.cnblogs.com/we8fans/p/14120372.html

版权声明:完美者 发表于 2020-12-16 12:47:50。
转载请注明:每日一题20201211(623. 在二叉树中增加一行) | 完美导航

暂无评论

暂无评论...