0919. Complete Binary Tree Inserter¶
题目信息¶
- 题号:
0919
- 难度:
Medium
- 主题:
设计题、完全二叉树、持续插入
- 原题:
- 重点:
构造函数接收一棵非空完全二叉树;每次
insert必须填入层序中的下一个空位并返回父节点值,所有调用持续修改同一棵树
题目重述¶
实现 CBTInserter 类。构造函数接收一棵非空完全二叉树的根节点 root。完全二叉树除最底层外每层都填满,最底层节点从左到右连续排列。
insert(val) 创建值为 val 的新节点,并把它放入能够继续保持完全二叉树结构的唯一位置,然后返回新节点父节点的值。get_root() 返回当前树的根节点。多次插入共享并永久更新同一棵树。
初始树节点数在 [1, 1000] 范围内,节点值和插入值在 [0, 5000] 范围内;insert 与 get_root 的总调用次数不超过 10^4。
自建示例¶
连续填充同一父节点的左右孩子:
输入:
["CBTInserter","insert","insert","get_root"]
[[[1,2,3,4,5]],[6],[7],[]]
输出:[null,3,3,[1,2,3,4,5,6,7]]
解释:初始节点 3 没有孩子。插入 6 和 7 时依次成为它的左、右孩子,因此两次 insert 都返回 3。
初始树只有根节点:
输入:
["CBTInserter","insert","get_root"]
[[[9]],[4],[]]
输出:[null,9,[9,4]]
解释:新节点 4 填入层序中的第一个空位,即根节点 9 的左孩子;insert 返回父节点值 9。