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 node
CBTInserter.insert(int v)will insert a
TreeNodeinto the tree with value
node.val = vso 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.
- The initial given tree is complete and contains between
CBTInserter.insertis called at most
10000times per test case.
Every value of a given or inserted node is between
题目给定了一个二叉树，要求写一个二叉树操作类，这个类可以初始化一个二叉树，插入二叉树，获取二叉树的根节点。可以使用数组来存储，就跟堆使用数组来表示二叉树一样，如果父节点的索引是 i，左子树则为 $2i$，右子树为 $2i+1$，初始化的时间复杂度是 $O(n)$，插入，获取根节点的复杂度是 $O(1)$。