首页 > itarticle > [leetcode] problem 919 – complete binary tree inserter

[leetcode] problem 919 – complete binary tree inserter

admin 11月 13, 2020 0

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:

  • CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
  • CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
  • CBTInserter.get_root() will return the head node of the tree.

Example

No.1

Input: inputs = [“CBTInserter”,”insert”,”get_root”], inputs = [[[1]],[2],[]]

Output: [null,1,[1,2]]

No.2

Input: inputs = [“CBTInserter”,”insert”,”insert”,”get_root”], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]

Output: [null,3,4,[1,2,3,4,5,6,7,8]]

Note

  1. The initial given tree is complete and contains between 1 and 1000 nodes.
  2. CBTInserter.insert is called at most 10000 times per test case.
  3. Every value of a given or inserted node is between 0 and 5000.

Code

1
2
3
4
5
6
 
public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
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
 
private TreeNode root;
private Queue<TreeNode> leaves;

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

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            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)
                leaves.offer(node);
        }
    }
}

public int insert(int v) {
    TreeNode leaf = new TreeNode(v);
    TreeNode parent = leaves.peek();

    if (parent.left == null)
        parent.left = leaf;
    else {
        parent.right = leaf;
        leaves.poll();
    }

    leaves.offer(leaf);
    return parent.val;
}

public TreeNode get_root() {
    return root;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能