Skip to content

Instantly share code, notes, and snippets.

@yokolet
Created September 10, 2019 19:36
Show Gist options
  • Save yokolet/afa881446150ce323492d31d30738f4d to your computer and use it in GitHub Desktop.
Save yokolet/afa881446150ce323492d31d30738f4d to your computer and use it in GitHub Desktop.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment