Problem
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
.
Solution 2: Deque
Using a deck to keep track of insertable nodes (potential parents) in order.
Time complexity: O(1) / O(n) first call
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua class CBTInserter { public: CBTInserter(TreeNode* root): root_(root), d_({root}) {} int insert(int v) { while (!d_.empty()) { TreeNode* r = d_.front(); if (r->left && r->right) { d_.push_back(r->left); d_.push_back(r->right); d_.pop_front(); } else if (r->left) { r->right = new TreeNode(v); return r->val; } else { r->left = new TreeNode(v); return r->val; } } } TreeNode* get_root() { return root_; } private: std::deque<TreeNode*> d_; TreeNode* root_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment