919_完全二叉树插入器

类型：树

• 919. 完全二叉树插入器 💛

  https://leetcode-cn.com/problems/complete-binary-tree-inserter/

  ❓ 实现一个完全二叉树类。支持以下操作：

  • 初始化

    CBTInserter(TreeNode root)

    使用头节点为 root 的树初始化该对象。

  • 结点插入

    CBTInserter.insert(int v)

    向完全二叉树对象中插入新结点，结点值为 v。返回新插入结点的父结点的值。

  • 返回头结点

    CBTInserter.get_root()

    返回头结点地址

  💡 队列

  我们可以用队列 queue 来存储完全二叉树，对于结点 n 来说，其左孩子是结点 2 * n + 1，其右孩子是结点 2 * n + 2。我们每次有新结点的时候就将其加入 queue 末尾。

  class CBTInserter(object):
      def __init__(self, root):
          self.deque = collections.deque()
          self.root = root
          q = collections.deque([root])
          while q:
              node = q.popleft()
              if not node.left or not node.right:
                  self.deque.append(node)
              if node.left:
                  q.append(node.left)
              if node.right:
                  q.append(node.right)
  
      def insert(self, v):
          node = self.deque[0]
          self.deque.append(TreeNode(v))
          if not node.left:
              node.left = self.deque[-1]
          else:
              node.right = self.deque[-1]
              self.deque.popleft()
          return node.val
  
      def get_root(self):
          return self.root