0919. Complete Binary Tree Inserter

题目信息

题号:

0919

难度:

Medium

主题:

设计题、完全二叉树、持续插入

原题:

LeetCode 0919

重点:

构造函数接收一棵非空完全二叉树;每次 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。