Illustration leetcode - 919. Complete binary tree inserter (difficulty: medium)

One 、 subject

Perfect binary tree Every floor （ Except for the last floor ） All completely filled （ namely , The number of nodes reaches the maximum ） Of , And all nodes are concentrated on the left as much as possible . Design an algorithm , Insert a new node into a complete binary tree , And keep it intact after insertion .

Realization CBTInserter class :

• CBTInserter(TreeNode root)  Use the header node as  root  Initialize the data structure for the given tree ;
• CBTInserter.insert(int v)  Insert a value of... Into the tree  Node.val == val  The new node  TreeNode. Keep the tree in the state of a complete binary tree , And return to the insert node  TreeNode  The value of the parent node of ;
• CBTInserter.get_root()  The head node of the tree will be returned .

Two 、 Example

2.1> Example 1：

【 Input 】
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
【 Output 】
[null, 1, 2, [1, 2, 3, 4]]
【 explain 】
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // return 1
cBTInserter.insert(4); // return 2
cBTInserter.get_root(); // return [1, 2, 3, 4]

Tips ：

• The number of nodes in the tree ranges from  [1, 1000]
• 0 <= Node.val <= 5000
• root  It's a perfect binary tree
• 0 <= val <= 5000
• Each test case calls at most  insert  and  get_root  operation  10^4  Time

3、 ... and 、 Their thinking

3.1> breadth-first + queue

First , According to the title requirements , First add data according to each layer , In the same layer , Add nodes from left to right . Then we can go through the queue （queue） To execute Breadth first traversal Nodes of each layer , In the process of traversing , then Left node is empty perhaps The right node is empty The node of , Put into another queue （queueInsertNode） in , For subsequent insert operation . As shown in the figure below ：

When we need to insert new nodes , First , Put the created new node into queueInsertNode In line , Used for the subsequent addition of new nodes . secondly , By calling peek() Method to get the queue header element , But this element will not be deleted from the queue . After getting the header element , Put the new node on the left or right side of the node , If it is placed on the right , It means that the left and right leaf nodes of the header element already exist , Then call poll() Method to set the element “ Kicked out ” queue . The specific operation is shown in the figure below ：

Four 、 Code implementation

4.1> breadth-first + queue

public class CBTInserter {
    private Queue<TreeNode> queueInsertNode;
    private TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queueInsertNode = new ArrayDeque<>();
        queue.offer(root);
        TreeNode node;
        while (!queue.isEmpty()) { //  Breadth first traversal 
            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) {
                queueInsertNode.offer(node);
            }
        }
    }

    public int insert(int val) {
        TreeNode newNode = new TreeNode(val);
        TreeNode node = queueInsertNode.peek();
        if (node.left == null) {
            node.left = newNode;
        } else if (node.right == null) {
            node.right = newNode;
            queueInsertNode.poll();
        }
        queueInsertNode.offer(newNode);
        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

That's all for today's article ：

Writing is not easy to , An article completed by the author in hours or even days , I only want to exchange you for a few seconds give the thumbs-up & Share .

More technical dry goods , Welcome everyone to follow the official account @ Java Muse 「 Dry cargo sharing , Update daily 」

Previous recommendation

The illustration LeetCode——731. My schedule II（ difficulty ： secondary ）https://mp.csdn.net/mp_blog/creation/editor/125884328 The illustration LeetCode——3. Longest substring without repeating characters （ difficulty ： secondary ）https://mp.csdn.net/mp_blog/creation/editor/125857066LeetCode Work: ——21. Merge two ordered lists （ difficulty ： Simple ）https://mp.csdn.net/mp_blog/creation/editor/125840103LeetCode Work: ——565. Array nesting （ difficulty ： secondary ）https://mp.csdn.net/mp_blog/creation/editor/125831251

Title source ： Power button （LeetCode）