Force buckle 919. Complete binary tree inserter

subject

Perfect binary tree Every floor （ Except for the last floor ） All completely filled （ namely , The number of nodes reaches the maximum ） Of , And all nodes are concentrated on the left as much as possible .

Design an algorithm , Insert a new node into a complete binary tree , And keep it intact after insertion .

Realization CBTInserter class :

CBTInserter(TreeNode root) Use the header node as root Initialize the data structure for the given tree ;
CBTInserter.insert(int v) Insert a value of... Into the tree Node.val == val The new node TreeNode. Keep the tree in the state of a complete binary tree , And return to the insert node TreeNode The value of the parent node of ;
CBTInserter.get_root() The head node of the tree will be returned .

Example

Input
[“CBTInserter”, “insert”, “insert”, “get_root”]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

explain
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // return 1
cBTInserter.insert(4); // return 2
cBTInserter.get_root(); // return [1, 2, 3, 4]

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/complete-binary-tree-inserter
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： Queue simulation

Java Realization

class CBTInserter {
    
    Queue<TreeNode> queue, candidate;
    TreeNode root;

    public CBTInserter(TreeNode root) {
    
        this.root = root;
        queue = new LinkedList<>();
        candidate = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
    
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
    
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
				// If the left subtree is empty or the right subtree is empty, add candidate queue 
                if (!(cur.left != null && cur.right != null)) candidate.offer(cur);
            }
        }
    }
    
    public int insert(int val) {
    
        TreeNode node  = candidate.peek();
        TreeNode var = new TreeNode(val);
        if (node.left == null) {
    
            node.left = var;
        } else {
    
        	// here , The right subtree also inserts nodes . The left and right subtrees of this node are not empty 
        	// therefore , From you to candidate Pop up this node in .
            node.right = var;
            candidate.poll();
        }
        candidate.offer(var);
        return node.val;

    }
    
    public TreeNode get_root() {
    
        return root;
    }
}