919. Complete Binary Tree Inserter

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.

Implement the CBTInserter class:

• CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.

• int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.

• TreeNode get_root() Returns the root node of the tree.

Example 1:

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

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

Constraints:

• The number of nodes in the tree will be in the range [1, 1000].

• 0 <= Node.val <= 5000

• root is a complete binary tree.

• 0 <= val <= 5000

• At most 104 calls will be made to insert and get_root.

Solution

Have no idea.

The key is to realize the relationship between the adding node and it parents.

Then the next mission is to classify the tree into a structure that we can easily access any node with index we want. We choose to use a list as the Data structure. And by BFS to classify the tree.

class CBTInserter {
    List<TreeNode> nodes;
    public CBTInserter(TreeNode root) {
        nodes = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            nodes.add(node);
            if(node.left != null){ 
                q.add(node.left);
            }
            if(node.right != null){
                q.add(node.right);
            }
        }
    }
    
    public int insert(int val) {
        int n = nodes.size();
        TreeNode node = new TreeNode(val);
        if((n-1)%2 == 0) {
            nodes.get((n-1)/2).left = node;
        }else{
            nodes.get((n-1)/2).right = node;
        }
        nodes.add(node);
        return nodes.get((n-1)/2).val;
    }
    
    public TreeNode get_root() {
        return nodes.get(0);   
    }
}