LeetCode 919. 完全二叉树插入器

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 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;Queue<TreeNode> q;// 用完全二叉树初始化的数据结构public CBTInserter(TreeNode root) {this.root=root;q=new LinkedList();q.offer(root);//bfswhile(!q.isEmpty()){TreeNode tmp=q.peek();// 维护上一层中从左边开始第一个左节点或者右节点为空的节点if(tmp.left==null || tmp.right==null){break;}q.offer(tmp.left);q.offer(tmp.right);q.poll();}}public int insert(int v) {TreeNode node=new TreeNode(v);TreeNode t=q.peek();if(t.left==null){//        5//       / \// 插入位置 t.left=node;}else{t.right=node;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