919.md

Complete Binary Tree Inserter

Description

link

---

Solution

• See Code

---

Code

Complexity T : O(1) M : O(n)

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

    def __init__(self, root: TreeNode):
        self.tree = [root]
        for i in self.tree:
            if i.left: self.tree.append(i.left)
            if i.right: self.tree.append(i.right)

    def insert(self, v):
        N = len(self.tree)
        self.tree.append(TreeNode(v))
        if N % 2:
            self.tree[(N - 1) // 2].left = self.tree[-1]
        else:
            self.tree[(N - 1) // 2].right = self.tree[-1]
        return self.tree[(N - 1) // 2].val

    def get_root(self):
        return self.tree[0]