A 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 noderoot
;CBTInserter.insert(int v)
will insert aTreeNode
into the tree with valuenode.val = v
so that the tree remains complete, and returns the value of the parent of the insertedTreeNode
;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:
- The initial given tree is complete and contains between
1
and1000
nodes. CBTInserter.insert
is called at most10000
times per test case.- Every value of a given or inserted node is between
0
and5000
.
Companies:
Google
Related Topics:
Tree
// OJ: https://leetcode.com/problems/complete-binary-tree-inserter/
// Author: github.com/lzl124631x
// Time:
// CBTInserter: O(N)
// insert: O(1)
// get_root: O(1)
// Space: O(N)
class CBTInserter {
private:
TreeNode *root;
queue<TreeNode*> q;
public:
CBTInserter(TreeNode* root): root(root) {
if (!root) return;
queue<TreeNode*> tmp;
tmp.push(root);
while (tmp.size()) {
root = tmp.front();
tmp.pop();
if (!root->left || !root->right) q.push(root);
if (root->left) tmp.push(root->left);
if (root->right) tmp.push(root->right);
}
}
int insert(int v) {
TreeNode *node = new TreeNode(v);
TreeNode *parent = q.front();
if (!parent->left) parent->left = node;
else {
parent->right = node;
q.pop();
}
q.push(node);
return parent->val;
}
TreeNode* get_root() {
return root;
}
};