919. Complete binary tree inserter: simple BFS application problem

Title Description

This is a LeetCode Upper 「919. Complete binary tree inserter 」 , The difficulty is 「 secondary 」.

Tag : 「 simulation 」、「BFS」、「 Tree traversal 」

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 .

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  
• root  It's a perfect binary tree
• Each test case calls at most   insert  and   get_root  operation     Time

BFS

Start with the array passed into the constructor root Conduct BFS Sequence traversal （ Because the sequence traversal order still needs to be preserved , So use a subscript pointer cur To simulate the out of line position ）.

about insert In terms of operation , We're going to be in the array （ Sequence traversal sequence ） First found in 「 There are left and right empty child nodes 」 Parent node fa, By finding fa The subscript of the process array of nodes increases monotonically , So you can use global variables idx Keep searching back , Every time a new node node Add to the current tree , Need to put node Add to end of array .

get_root Operation always returns the first element of the array .

Java Code ：

class CBTInserter {
    List<TreeNode> list = new ArrayList<>();
    int idx = 0;
    public CBTInserter(TreeNode root) {
        list.add(root);
        int cur = 0;
        while (cur < list.size()) {
            TreeNode node = list.get(cur);
            if (node.left != null) list.add(node.left);
            if (node.right != null) list.add(node.right);
            cur++;
        }
    }
    public int insert(int val) {
        TreeNode node = new TreeNode(val);
        while (list.get(idx).left != null && list.get(idx).right != null) idx++;
        TreeNode fa = list.get(idx);
        if (fa.left == null) fa.left = node;
        else if (fa.right == null) fa.right = node;
        list.add(node);
        return fa.val;
    }
    public TreeNode get_root() {
        return list.get(0);
    }
}

TypeScript Code ：

class CBTInserter {
    list: TreeNode[] = new Array<TreeNode>()
    idx: number = 0
    constructor(root: TreeNode | null) {
        this.list.push(root)
        let cur = 0
        while (cur < this.list.length) {
            const node = this.list[cur]
            if (node.left != null) this.list.push(node.left)
            if (node.right != null) this.list.push(node.right)
            cur++
        }
    }
    insert(val: number): number {
        const node = new TreeNode(val)
        while (this.list[this.idx].left != null && this.list[this.idx].right != null) this.idx++
        const fa = this.list[this.idx]
        if (fa.left == null) fa.left = node
        else if (fa.right == null) fa.right = node
        this.list.push(node)
        return fa.val
    }
    get_root(): TreeNode | null {
        return this.list[0]
    }
}

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.919 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases