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``。 自建示例 -------- 连续填充同一父节点的左右孩子: .. code-block:: text 输入: ["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。 初始树只有根节点: .. code-block:: text 输入: ["CBTInserter","insert","get_root"] [[[9]],[4],[]] 输出:[null,9,[9,4]] 解释:新节点 4 填入层序中的第一个空位,即根节点 9 的左孩子;insert 返回父节点值 9。