LeetCode往完全二叉树添加节点
剑指 Offer II 043. 往完全二叉树添加节点
完全二叉树是每一层(除最后一层外)都是完全填充(即,节点数达到最大,第 n 层有 2n-1 个节点)的,并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter,它支持以下几种操作:
CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构;
CBTInserter.insert(int v) 向树中插入一个新节点,节点类型为 TreeNode,值为 v 。使树保持完全二叉树的状态,并返回插入的新节点的父节点的值;
CBTInserter.get_root() 将返回树的根节点。
输入:inputs = [“CBTInserter”,“insert”,“get_root”], inputs = [[[1]],[2],[]]
输出:[null,1,[1,2]]
来源:LeetCode
首先想到的就是层序遍历,利用层序遍历找到符合条件的父节点,查看它的左孩子和右孩子,如果左孩子为null,就新添加节点作为它的左孩子,如果左孩子不为null,右孩子为null,就添加其右孩子节点。
class CBTInserter {
TreeNode root;
public CBTInserter(TreeNode root) {
this.root=root;
}
public int insert(int v) {
int ans=0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
if(root==null){
return v;
}
TreeNode t = root;
while(!queue.isEmpty()){
t = queue.poll();
if(t.left!=null)
{
queue.offer(t.left);
}
else
{
TreeNode tleft = new TreeNode(v);
t.left=tleft;
ans = t.val;
break;
}
if(t.right!=null){
queue.offer(t.right);
}
if(t.right==null){
TreeNode tright = new TreeNode(v);
t.right = tright;
ans = t.val;
break;
}
}
return ans;
}
public TreeNode get_root() {
return root;
}
}
注意t应该是队首的节点。
在编码的时候碰到了问题:如果将queue定义为全局变量就会导致有的节点的右孩子考虑不到(因为用了break操作,就有可能不会去判断某个节点的右孩子是否为null,而是直接下一个节点)。
官方题解中给出了另一种解法。
申请两个队列,分别进行层序遍历和选出符合条件的父节点。
每次要插入元素时就从候选队列找到队首元素,将插入节点作为它的孩子节点,并将孩子节点也要进入队列。
当然要注意,如果队首的元素左右孩子节点都已经不为null,那该节点就应该出队列。
class CBTInserter {
TreeNode root;
Queue<TreeNode> cur = new ArrayDeque<TreeNode>();
public CBTInserter(TreeNode root) {
this.root=root;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
TreeNode t = root;
queue.offer(root);
while(!queue.isEmpty()){
t = queue.poll();
if(t.left!=null)
{
queue.offer(t.left);
}
if(t.right!=null){
queue.offer(t.right);
}
if(t.left==null||t.right==null){
cur.offer(t);
}
}
}
public int insert(int v) {
if(root==null){
return v;
}
TreeNode res = cur.peek();
TreeNode node = new TreeNode(v);
if(res.left==null)
{
res.left=node;
}
else{
res.right=node;
cur.poll();
}
cur.offer(node);
return res.val;
}
public TreeNode get_root() {
return root;
}
}
千万千万注意一定要将新的节点(既没有左孩子也没有右孩子)加入到cur队列里,否则有可能会造成cur队列为null。
CBTInserter(TreeNode root)方法里面的层序遍历只能遍历题目给出的树,将其符合的节点加入cur。