标签
树
设计
二叉树
日期
Oct 15, 2022
剑指 Offer II 043. 往完全二叉树添加节点
题目描述
完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第
n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。设计一个用完全二叉树初始化的数据结构
CBTInserter，它支持以下几种操作：CBTInserter(TreeNode root)使用根节点为root的给定树初始化该数据结构；
CBTInserter.insert(int v)向树中插入一个新节点，节点类型为TreeNode，值为v。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root()将返回树的根节点。
示例 1：
示例 2：
题目解析
思路：
- 题目要求需要返回根节点，就可以使用数组或者队列来存储该完全二叉树，我选择的是数组
- 构造器正常初始化，先将根节点加入
list，然后遍历左右节点加入list
- 插入的时候我们需要先找到最后一个节点，并判断它的左右子树哪一个为空，为空的则将新节点插入，并加入
list，返回其节点值
- 获取根节点的话就直接
list.get(0)方法即可