完全二叉树插入器

/*
题目思路：
1. 使用队列层次遍历树节点并存储在List中。
2. 使用流来筛选出没有两个子节点的节点，作为插入的候选位置。
3. 插入节点时，检查第一个候选节点，如果其左子节点为空则插入到左子节点，否则插入到右子节点。
4. 插入后，更新候选位置列表。
*/

import java.util.*;
import java.util.stream.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class CBTInserter {
    private TreeNode root;
    private List<TreeNode> list;

    public CBTInserter(TreeNode root) {
        this.root = root;
        list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 初始化list，保存树的层次遍历节点
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    public int insert(int v) {
        TreeNode newNode = new TreeNode(v);
        for (TreeNode node : list) {
            if (node.left == null) {
                node.left = newNode;
                break;
            } else if (node.right == null) {
                node.right = newNode;
                break;
            }
        }
        list.add(newNode);
        return list.stream()
                    .filter(node -> node.left == newNode || node.right == newNode)
                    .findFirst()
                    .map(node -> node.val)
                    .get();
    }

    public TreeNode get_root() {
        return root;
    }
}