模板网站建设珠海,wordpress发布工具,做汽配找哪个网站好,互联网行业最新资讯完全二叉树是每一层#xff08;除最后一层外#xff09;都是完全填充#xff08;即#xff0c;节点数达到最大#xff09;的#xff0c;并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter#xff0c;它支持以下几种操作#xf…完全二叉树是每一层除最后一层外都是完全填充即节点数达到最大的并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter它支持以下几种操作
CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构CBTInserter.insert(int v) 向树中插入一个新节点节点类型为 TreeNode值为 v 。使树保持完全二叉树的状态并返回插入的新节点的父节点的值CBTInserter.get_root() 将返回树的头节点。 示例 1输入inputs [CBTInserter,insert,get_root], inputs [[[1]],[2],[]]
输出[null,1,[1,2]]
示例 2输入inputs [CBTInserter,insert,insert,get_root], inputs [[[1,2,3,4,5,6]],[7],[8],[]]
输出[null,3,4,[1,2,3,4,5,6,7,8]]题目分析
由于插入操作要找到最后一层的第一个空缺的位置所以很自然的就想到了使用层序遍历的方法由于插入函数返回的是插入位置的父结点所以在层序遍历的时候只要遇到某个结点的左子结点或者右子结点不存在则跳出循环则这个残缺的父结点刚好就在队列的首位置。
那么在插入函数时只要取出这个残缺的父结点判断若其左子结点不存在说明新的结点要连接在左子结点上否则将新的结点连接在右子结点上并把此时的左右子结点都存入队列中并将之前的队首元素移除队列即可。
这道题目是层序遍历的变种。关键是实现插入时返回对应的头节点。
使用队列队头维护上一层中从左边开始第一个左节点或者右节点为空的节点。
题目并不是让我们实现一个完全二叉树而是给定一个完全二叉树的头实现插入器。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class CBTInserter {TreeNode root;QueueTreeNode q;// 用完全二叉树初始化的数据结构public CBTInserter(TreeNode root) {this.rootroot;qnew LinkedList();q.offer(root);//bfswhile(!q.isEmpty()){TreeNode tmpq.peek();// 维护上一层中从左边开始第一个左节点或者右节点为空的节点if(tmp.leftnull || tmp.rightnull){break;}q.offer(tmp.left);q.offer(tmp.right);q.poll();}}public int insert(int v) {TreeNode nodenew TreeNode(v);TreeNode tq.peek();if(t.leftnull){// 5// / \// 插入位置 t.leftnode;}else{t.rightnode;q.offer(t.left);q.offer(t.right);//出队转移到下一个不完全的节点q.poll();}return t.val;}public TreeNode get_root() {return root;}
}/*** Your CBTInserter object will be instantiated and called as such:* CBTInserter obj new CBTInserter(root);* int param_1 obj.insert(v);* TreeNode param_2 obj.get_root();*/
文章参考
https://www.cnblogs.com/wwj99/p/12298419.html
