# 919. Complete Binary Tree Inserter

complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Write a data structure `CBTInserter` that is initialized with a complete binary tree and supports the following operations:

• `CBTInserter(TreeNode root)` initializes the data structure on a given tree with head node `root`;
• `CBTInserter.insert(int v)` will insert a `TreeNode` into the tree with value `node.val = v` so that the tree remains complete, and returns the value of the parent of the inserted `TreeNode`;
• `CBTInserter.get_root()` will return the head node of the tree.

Example 1:

``````Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]
``````

Example 2:

``````Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]
``````

Note:

1. The initial given tree is complete and contains between `1` and `1000` nodes.
2. `CBTInserter.insert` is called at most `10000` times per test case.
3. Every value of a given or inserted node is between `0` and `5000`.

``````class CBTInserter {
public:
CBTInserter(TreeNode* root) {
tree_root = root;
q.push(root);
while (!q.empty()) {
auto t = q.front();
if (!t->left || !t->right) break;
q.push(t->left);
q.push(t->right);
q.pop();
}
}
int insert(int v) {
TreeNode *node = new TreeNode(v);
auto t = q.front();
if (!t->left) t->left = node;
else {
t->right = node;
q.push(t->left);
q.push(t->right);
q.pop();
}
return t->val;
}
TreeNode* get_root() {
return tree_root;
}

private:
TreeNode *tree_root;
queue<TreeNode*> q;
};
``````

``````class CBTInserter {
public:
CBTInserter(TreeNode* root) {
tree_root = root;
}
int insert(int v) {
queue<TreeNode*> q{{tree_root}};
TreeNode *node = new TreeNode(v);
while (!q.empty()) {
auto t = q.front(); q.pop();
if (t->left) q.push(t->left);
else {
t->left = node;
return t->val;
}
if (t->right) q.push(t->right);
else {
t->right = node;
return t->val;
}
}
return 0;

}
TreeNode* get_root() {
return tree_root;
}

private:
TreeNode *tree_root;
};
``````

``````class CBTInserter {
public:
CBTInserter(TreeNode* root) {
tree.push_back(root);
for (int i = 0; i < tree.size(); ++i) {
if (tree[i]->left) tree.push_back(tree[i]->left);
if (tree[i]->right) tree.push_back(tree[i]->right);
}
}
int insert(int v) {
TreeNode *node = new TreeNode(v);
int n = tree.size();
tree.push_back(node);
if (n % 2 == 1) tree[(n - 1) / 2]->left = node;
else tree[(n - 1) / 2]->right = node;
return tree[(n - 1) / 2]->val;
}
TreeNode* get_root() {
return tree[0];
}

private:
vector<TreeNode*> tree;
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/919

Count Complete Tree Nodes

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

https://leetcode.com/problems/complete-binary-tree-inserter/discuss/178424/C%2B%2BJavaPython-O(1)-Insert