[寻求一些提示]将排序的数组插入到构造的BST中

Question

我有一个家庭作业问题是想出一个有效的算法，将一个有 m 个元素的排序数组插入到一个有 n 个元素的（n 个不平衡）二叉搜索树中，这样总的运行时间是 O( m+n) 而不是 m*O(n)。纠结了半天，还是没有明确的方向，所以写下post，求大神指点

Answer 1

您可以使用以下算法：

对BST中的节点进行一次中序遍历，并保留本次遍历中访问过的前一个节点的引用。前一个节点以 null 开始。保持以下不变量：当前节点没有左child，然后前一个节点为空或祖先，或者当前节点有左child，前一个节点是后代.
当排序数组中的下一个值小于当前节点时，则为该数组值插入一个新节点作为当前节点的左child（当有没有左 child) 或作为前一个节点的右 child（当当前节点有左 child 时）。使新创建的节点成为“前一个”节点。递增数组中的索引，并重复此步骤，直到排序后的数组中的下一个值不小于当前节点。
中序遍历得到下一对(previous,current)，重复步骤2，直到中序遍历完成或者所有数组值都插入完毕
如果还有数组值，则追加到中序遍历找到的最后一个节点的右边，一直向右加深...

这是 JavaScript 中的一个实现：

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
    add(val) {
        if (val < this.val) {
            if (!this.left) this.left = new Node(val);
            else this.left.add(val);
        } else {
            if (!this.right) this.right = new Node(val);
            else this.right.add(val);
        }
    }
    * inorder() {  // recursive
        if (this.left) yield * this.left.inorder();
        yield this;
        if (this.right) yield * this.right.inorder();
    }
    addSorted(arr) {
        let i = 0; // index in arr
        let prev = null; // follows behind node
        for (let node of this.inorder()) {
            while (arr[i] < node.val) {
                if (!node.left) prev = node.left = new Node(arr[i++]); 
                else prev = prev.right = new Node(arr[i++]);
                if (i >= arr.length) return;
            }
            prev = node;
        }
        while (i < arr.length) {
            prev = prev.right = new Node(arr[i++]);
        }
    }
}

// Demo
// Initialise tree and print the inorder traversal
let root = new Node(40);
for (let i of [30, 70, 20, 35, 60, 80, 5, 55]) root.add(i);
for (let node of root.inorder()) console.log(node.val);

// Apply the algorithm for adding a sorted list of values
root.addSorted([1, 2, 8, 22, 38, 39, 43, 50, 51, 59, 72, 100]);
console.log("after having added sorted array:");
for (let node of root.inorder()) console.log(node.val);

[寻求一些提示]将排序的数组插入到构造的BST中

[Ask for some hints]Inserting a sorted array into a constructed BST

arrays

algorithm

runtime

insert

binary-search-tree