合并 2 棵 AVL 树，其中一棵有损坏的节点
Merge 2 AVL trees with corrupted nodes in one of them
假设我们有 2 棵 AVL 树（使用方法 insert(key) 和 delete(key)），但是 其中一个 存在损坏的节点（数量损坏的节点数远远少于该树中的节点总数。
我们想将 2 棵 AVL 树合并成 1 棵 AVL 树，以便删除损坏的节点（我们有损坏节点的键列表）。
“朴素”算法是（假设树 1 包含损坏的节点）：对于每个损坏的节点，将其从树 1 中删除。然后从树中插入所有剩余节点1到树2，所以最终的AVL树就是我们想要的“合并”树。
现在的问题是想出一种更有效的方法来合并 2 棵树，比上面的 朴素算法 更好。
有人知道吗？感谢您的帮助！
二叉搜索树可以在线性时间 O(N) 内按递增顺序列出其节点。您可以组织一个合并过程，在该过程中同时枚举两棵树的节点，以全局顺序获取节点（并删除损坏的节点）。
如果将排序后的元素存储在数组中，则可以在线性时间内转换为新的平衡 BST。您只需设置所有平衡因子即可使其成为 AVL。
我怀疑是否可以在不首先合并到中间数组的情况下构建新树。 （只需要是一个指针数组即可。）
假设我们有 2 棵 AVL 树（使用方法 insert(key) 和 delete(key)），但是 其中一个 存在损坏的节点（数量损坏的节点数远远少于该树中的节点总数。
我们想将 2 棵 AVL 树合并成 1 棵 AVL 树，以便删除损坏的节点（我们有损坏节点的键列表）。
“朴素”算法是（假设树 1 包含损坏的节点）：对于每个损坏的节点，将其从树 1 中删除。然后从树中插入所有剩余节点1到树2，所以最终的AVL树就是我们想要的“合并”树。
现在的问题是想出一种更有效的方法来合并 2 棵树，比上面的 朴素算法 更好。
有人知道吗？感谢您的帮助！
二叉搜索树可以在线性时间 O(N) 内按递增顺序列出其节点。您可以组织一个合并过程，在该过程中同时枚举两棵树的节点，以全局顺序获取节点（并删除损坏的节点）。
如果将排序后的元素存储在数组中，则可以在线性时间内转换为新的平衡 BST。您只需设置所有平衡因子即可使其成为 AVL。
我怀疑是否可以在不首先合并到中间数组的情况下构建新树。 （只需要是一个指针数组即可。）