测试岗位也越来卷了，除了基本的功能测试外，还要有编程基础、脚本经验才脱颖而出。

怎么才能提高我们的编程能力呢，刷LeetCode是最佳的途径之一，话不多数,刷题走起~

一、题目描述：

• 题目内容

  

• 题目示例

  

• 题目解析

  • 树中节点数量范围为 [1, 1000] 
  • 0 <= Node.val <= 5000
  • root 是完全二叉树
  • 0 <= val <= 5000 
  • 每个测试用例最多调用 insert 和 get_root 操作 104 次

二、思路分析：

读取本题题目，要求我们构造一个完全二叉树，实现insert方法在完全二叉树中插入新节点，并返回器父节点。知道题目题意后，我们还需要明确几个知识点：

• 完全二叉树是啥？：完全二叉树又称为满二叉树，深度为i层有2^i-1的节点的二叉树
• 题目给出的root是完全二叉树

在构造完全二叉树插入器之前，我们要先实现__init__(self,root)方法，获取到未满二叉树节点列表。二叉树遍历有深度遍历dfs和广度遍历bfs两种，根据本题的要求我们需要记录未满度数为2的节点列表，以便提供给insert方法使用。

• 遍历二叉树选用广度优先遍历，则使用列表来模拟队列添加每一层的节点，定义一个从root指针开始的列表self.bfs(self.root)，pop出列表中父节点cur，添加其左孩子节点或者右孩子节点到队列中,直到self.bfs为空
• 当cur节点其左孩子或者右孩子节点只有任意一个或都为空时，则记录未满度数为2的节点列表self.tree.append(cur)
• 当cur节点的左孩子存在时，则self.bfs列表将cur.left节点添加
• 当cur节点的右孩子存在时，则self.bfs列表将cur.right节点添加

对二叉树root使用bfs方法构造完成后，进行实现insert方法。insert方法需要找到未满度数为2的节点然后将新节点添加到二叉树root中，并返回父节点

• 使用TreeNode对insert中参数val构造一个新节点
• 在__init__()构造函数中得到记录的未满度数为2的节点self.tree表中index=0的就是当前的父节点cur,返回其值
• 当cur.left为空时，则新节点添加到cur的左节点位置上
• 当cur.left已经存在时，则新节点添加到cur的右节点位置上，并且self.tree删除当前的度数为2的cur节点

因为root指针始终指在二叉树的头节点，因此get_root方法只需要饭self.root即可

根据以上思路，我们使用Python来实现完全二叉树插入器，代码如下：

class CBTInserter(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.root = root
        self.tree = []
        self.bfs = [self.root]

        while self.bfs:
            cur = self.bfs.pop(0)
            if not (cur.left and cur.right) :
                self.tree.append(cur)
            if cur.left:
                self.bfs.append(cur.left)
            if cur.right:
                self.bfs.append(cur.right)
            
    def insert(self, val):
        """
        :type val: int
        :rtype: int
        """
        child = TreeNode(val)
        # self.tree_ = self.tree
        cur = self.tree[0]
        res = cur.val
        if not cur.left:
            cur.left = child 
        else:
            cur.right = child
            self.tree.pop(0)
        self.tree.append(child)
        return res

    def get_root(self):
        """
        :rtype: TreeNode
        """
        return self.root

三、总结：

本题考察我们对二叉树广度优先遍历方法熟练运用，得到度数未满2的节点列表，在插入新节点时，只需要推出最开头节点cur，判断cur.left和cur.right任意一个为空，则将新节点添加到二叉树上

• 时间复杂度:CBTInserter初始化O(n)，insert O(1)
• 空间复杂度:O(n+q) q为insert调用次数.

以上是本期内容，欢迎大佬们点赞评论，下期见~~