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 queue = new ArrayDeque();
        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 cur = new ArrayDeque();
    public CBTInserter(TreeNode root) {
        this.root=root;
        Queue queue = new ArrayDeque();
        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。