松江网站建设公司怎么样,成都建设官方网站,wordpress做后端,安义南昌网站建设公司文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;完全二叉树插入器
出处#xff1a;919. 完全二叉树插入器
难度
6 级
题目描述
要求
完全二叉树是每一层#xff08;除最后一层外#xff09;都… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题完全二叉树插入器
出处919. 完全二叉树插入器
难度
6 级
题目描述
要求
完全二叉树是每一层除最后一层外都是完全填充的并且所有的结点都尽可能地集中在左侧。
设计一种算法将一个新结点插入到一个完全二叉树中并在插入后保持完全二叉树。
实现 CBTInserter \texttt{CBTInserter} CBTInserter 类: CBTInserter(TreeNode root) \texttt{CBTInserter(TreeNode root)} CBTInserter(TreeNode root) 使用完全二叉树的根结点 root \texttt{root} root 初始化数据结构 int insert(int v) \texttt{int insert(int v)} int insert(int v) 向树中插入一个值为 val \texttt{val} val 的新结点使树保持完全二叉树的状态并返回插入结点的父结点的值 TreeNode get_root() \texttt{TreeNode get\_root()} TreeNode get_root() 返回树的头结点。
示例
示例 1 输入 [CBTInserter, insert, insert, get_root] \texttt{[CBTInserter, insert, insert, get\_root]} [CBTInserter, insert, insert, get_root] [[[1, 2]], [3], [4], []] \texttt{[[[1, 2]], [3], [4], []]} [[[1, 2]], [3], [4], []] 输出 [null, 1, 2, [1, 2, 3, 4]] \texttt{[null, 1, 2, [1, 2, 3, 4]]} [null, 1, 2, [1, 2, 3, 4]] 解释 CBTInserter cBTInserter new CBTInserter([1, 2]); \texttt{CBTInserter cBTInserter new CBTInserter([1, 2]);} CBTInserter cBTInserter new CBTInserter([1, 2]); cBTInserter.insert(3); \texttt{cBTInserter.insert(3);} cBTInserter.insert(3); // 返回 1 \texttt{1} 1 cBTInserter.insert(4); \texttt{cBTInserter.insert(4);} cBTInserter.insert(4); // 返回 2 \texttt{2} 2 cBTInserter.get_root(); \texttt{cBTInserter.get\_root();} cBTInserter.get_root(); // 返回 [1, 2, 3, 4] \texttt{[1, 2, 3, 4]} [1, 2, 3, 4]
数据范围
树中结点数目在范围 [1, 1000] \texttt{[1, 1000]} [1, 1000] 内 0 ≤ Node.val ≤ 5000 \texttt{0} \le \texttt{Node.val} \le \texttt{5000} 0≤Node.val≤5000 root \texttt{root} root 是完全二叉树 0 ≤ val ≤ 5000 \texttt{0} \le \texttt{val} \le \texttt{5000} 0≤val≤5000最多调用 10 4 \texttt{10}^\texttt{4} 104 次 insert \texttt{insert} insert 和 get_root \texttt{get\_root} get_root
解法
思路和算法
这道题的解法不唯一。一种常规的解法是维护完全二叉树中的结点数每次插入结点时根据结点数定位到插入结点的位置。当完全二叉树中有 n n n 个结点时该解法每次插入操作的时间复杂度是 O ( log n ) O(\log n) O(logn)。
利用完全二叉树的性质可以将每次插入操作的时间复杂度降低到 O ( 1 ) O(1) O(1)。
由于完全二叉树的结点插入顺序和层序遍历相同因此在初始化时可以使用层序遍历访问完全二叉树中的每个结点。每次插入的结点的父结点一定是层序遍历访问到的第一个存在空子结点的结点父结点满足两个子结点都为空或者只有右子结点为空。如果父结点的两个子结点都为空则插入的结点作为父结点的左子结点如果父结点的子结点中只有右子结点为空则插入的结点作为父结点的右子结点。
如果一个结点的两个子结点都不为空则下一个插入的结点的父结点一定是层序遍历顺序中当前结点后面的结点。因此维护完全二叉树的根结点和队列即可实现每次插入使用 O ( 1 ) O(1) O(1) 的时间完成。
初始化时将根结点入队列然后执行如下操作如果队首结点的两个子结点都不为空则将队首结点出队列并将队首结点的左子结点和右子结点依次入队列。重复该操作直到队首结点的两个子结点中至少有一个为空。
对于插入结点操作使用给定的结点值创建新结点此时队首结点即为插入结点的父结点。执行如下操作。 判断父结点的左子结点是否为空执行相应的操作。 如果父结点的左子结点为空则将新结点作为父结点的左子结点。 如果父结点的左子结点不为空则将新结点作为父结点的右子结点然后将父结点出队列并将父结点的左子结点和右子结点依次入队列。 返回父结点值。
对于返回根结点操作返回完全二叉树的根结点即可。
代码
class CBTInserter {TreeNode root;QueueTreeNode queue;public CBTInserter(TreeNode root) {this.root root;queue new ArrayDequeTreeNode();queue.offer(root);while (queue.peek().left ! null queue.peek().right ! null) {TreeNode node queue.poll();queue.offer(node.left);queue.offer(node.right);}}public int insert(int val) {TreeNode insertNode new TreeNode(val);TreeNode node queue.peek();if (node.left null) {node.left insertNode;} else {node.right insertNode;queue.poll();queue.offer(node.left);queue.offer(node.right);}return node.val;}public TreeNode get_root() {return root;}
}复杂度分析 时间复杂度构造方法的时间复杂度是 O ( n ) O(n) O(n)插入结点操作和返回根结点操作的时间复杂度都是 O ( 1 ) O(1) O(1)其中 n n n 是二叉树的结点数。构造方法需要对完全二叉树层序遍历需要 O ( n ) O(n) O(n) 的时间。插入结点操作将新结点作为父结点的子结点可能有队列操作需要 O ( 1 ) O(1) O(1) 的时间。返回根结点操作直接返回完全二叉树的根结点需要 O ( 1 ) O(1) O(1) 的时间。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。需要存储完全二叉树以及使用队列存储完全二叉树中的子结点不完全的结点。
