上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class CBTInserter {
public:
CBTInserter(TreeNode* root) {
}
int insert(int val) {
}
TreeNode* get_root() {
}
};
/**
* Your CBTInserter object will be instantiated and called as such:
* CBTInserter* obj = new CBTInserter(root);
* int param_1 = obj->insert(val);
* TreeNode* param_2 = obj->get_root();
*/
golang 解法, 执行用时: 8 ms, 内存消耗: 6.6 MB, 提交时间: 2022-11-23 16:14:33
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type CBTInserter struct {
root *TreeNode
candidate []*TreeNode
}
func Constructor(root *TreeNode) CBTInserter {
q := []*TreeNode{root}
candidate := []*TreeNode{}
for len(q) > 0 {
node := q[0]
q = q[1:]
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
if node.Left == nil || node.Right == nil {
candidate = append(candidate, node)
}
}
return CBTInserter{root, candidate}
}
func (c *CBTInserter) Insert(val int) int {
child := &TreeNode{Val: val}
node := c.candidate[0]
if node.Left == nil {
node.Left = child
} else {
node.Right = child
c.candidate = c.candidate[1:]
}
c.candidate = append(c.candidate, child)
return node.Val
}
func (c *CBTInserter) Get_root() *TreeNode {
return c.root
}
/**
* Your CBTInserter object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Insert(val);
* param_2 := obj.Get_root();
*/
golang 解法, 执行用时: 12 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-23 16:13:48
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type CBTInserter struct {
root *TreeNode
cnt int
}
func Constructor(root *TreeNode) CBTInserter {
q := []*TreeNode{root}
cnt := 0
for len(q) > 0 {
cnt++
node := q[0]
q = q[1:]
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
return CBTInserter{root, cnt}
}
func (c *CBTInserter) Insert(val int) int {
c.cnt++
child := &TreeNode{Val: val}
node := c.root
for i := bits.Len(uint(c.cnt)) - 2; i > 0; i-- {
if c.cnt>>i&1 == 0 {
node = node.Left
} else {
node = node.Right
}
}
if c.cnt&1 == 0 {
node.Left = child
} else {
node.Right = child
}
return node.Val
}
func (c *CBTInserter) Get_root() *TreeNode {
return c.root
}
/**
* Your CBTInserter object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Insert(val);
* param_2 := obj.Get_root();
*/
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2022-11-23 16:12:49
# 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.root = root
self.cnt = 0
q = deque([root])
while q:
self.cnt += 1
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
def insert(self, val: int) -> int:
self.cnt += 1
child = TreeNode(val)
node = self.root
highbit = self.cnt.bit_length() - 1
for i in range(highbit - 1, 0, -1):
if self.cnt & (1 << i):
node = node.right
else:
node = node.left
if self.cnt & 1:
node.right = child
else:
node.left = child
return node.val
def get_root(self) -> TreeNode:
return self.root
# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(val)
# param_2 = obj.get_root()
python3 解法, 执行用时: 64 ms, 内存消耗: 15.9 MB, 提交时间: 2022-11-23 16:11:58
# 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.root = root
self.candidate = deque()
q = deque([root])
while q:
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if not (node.left and node.right):
self.candidate.append(node)
def insert(self, val: int) -> int:
candidate_ = self.candidate
child = TreeNode(val)
node = candidate_[0]
ret = node.val
if not node.left:
node.left = child
else:
node.right = child
candidate_.popleft()
candidate_.append(child)
return ret
def get_root(self) -> TreeNode:
return self.root
# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(val)
# param_2 = obj.get_root()
