919. Complete Binary Tree Inserter

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class CBTInserter {

    private final TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
    }

    public int insert(int v) {
        TreeNode leftmost = null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (i == queue.size()) {
                    leftmost = node;
                }
                if (node.left == null) {
                    node.left = new TreeNode(v);
                    return node.val;
                } else {
                    queue.offer(node.left);
                }
                if (node.right == null) {
                    node.right = new TreeNode(v);
                    return node.val;
                } else {
                    queue.offer(node.right);
                }
            }
        }

        leftmost.left = new TreeNode(v);
        return leftmost.val;
    }

    public TreeNode get_root() {
        return root;
    }

}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class CBTInserter {

    private final List<TreeNode> list;
    private int lastIndex;

    public CBTInserter(TreeNode root) {
        this.list = new ArrayList<>();
        list.add(root);
        int index = 0;

        // 确保遍历完所有节点
        while (index < list.size()) {
            TreeNode node = list.get(index);
            if (node.left != null) {
                list.add(node.left);
            }
            if (node.right != null) {
                list.add(node.right);
            }

            index++;
        }
    }

    public int insert(int v) {
        TreeNode newNode = new TreeNode(v);
        while (list.get(lastIndex).left != null && list.get(lastIndex).right != null) {
            lastIndex++;
        }

        TreeNode parentNode = list.get(lastIndex);
        if (parentNode.left == null) {
            parentNode.left = newNode;
        } else if (parentNode.right == null) {
            parentNode.right = newNode;
        }

        list.add(newNode);
        return parentNode.val;
    }

    public TreeNode get_root() {
        return list.get(0);
    }
    
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class CBTInserter {

    private final TreeNode root;
    private final Queue<TreeNode> candidateQueue; // 队列中仅保留可插入子节点的节点

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.candidateQueue = new LinkedList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

            if (node.left == null || node.right == null) {
                candidateQueue.offer(node);
            }
        }
    }

    public int insert(int val) {
        TreeNode child = new TreeNode(val);
        TreeNode node = candidateQueue.peek(); // 取出队首节点
        if (node.left == null) {
            node.left = child;
        } else { // 注意此处并未检查是否为完全二叉树，如果入参 root 不是完全二叉树，则 node.right 有不为空，会覆盖子节点，导致错误
            node.right = child;
            candidateQueue.poll();
        }
        candidateQueue.offer(child);

        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }

}

919 存在错误的测试用例，即 root 不是完全二叉树，导致不能 AC，需要等官方修复。

References

919. Complete Binary Tree Inserter
剑指 Offer II 043. 往完全二叉树添加节点