CBTInserter.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CBTInserter {
    private TreeNode root = null;
    private List<TreeNode> memo = new ArrayList<>();

    public CBTInserter(TreeNode root) {
        this.root = root;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            this.memo.add(cur);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    public int insert(int v) {
        int n = this.memo.size();
        TreeNode p = this.memo.get((n - 1)/2);
        if (n % 2 == 1) {
            p.left = new TreeNode(v);
            this.memo.add(p.left);
        } else {
            p.right = new TreeNode(v);
            this.memo.add(p.right);
        }
        return p.val;
    }

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