Leetcode--Java--919. 完全二叉树插入器

二叉树的堆式存储 + 完全二叉树性质 + 层序遍历

用数组来存储完全二叉树，从0开始编号的奇偶数规律。插入一个结点后，如果结点总数是奇数，则一定插在右结点。反之偶数，则一定插在左结点（画图不难发现）

class CBTInserter {
    List list;
    public CBTInserter(TreeNode root) {
        if (root == null) {
            return;
        }
        list = new ArrayList<>();
        Deque q = new linkedList<>();
        //层序遍历来初始化完全二叉树（一行一行放入数组）
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            list.add(node);
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
        }
    }
    
    public int insert(int val) {
        //直接插入，然后根据结点总数判断插入的是左结点还是右节点
        TreeNode node = new TreeNode(val);
        list.add(node);
        //根据完全二叉树性质求父节点位置，先除2，记得要减一，因为从0开始的
        int parent = list.size() / 2 - 1;
        if (list.size() % 2 == 0) {
            list.get(parent).left = node;
        }else {
            list.get(parent).right = node;
        }
        return list.get(parent).val;
    }
    
    public TreeNode get_root() {
        //数组空的话，就是null，否则返回第一个就是根结点
        return list.isEmpty() ? null : list.get(0);
    }
}