我得到了两个二进制搜索树。例如，A和B。接下来，我被要求从树A中删除树B。
删除是指从A中删除B中存在的所有节点。注意：B不一定是A的子树。
例如： A：
50 / \ 10 75 / / \ 1 60 90
B：
10 / \ 1 75
结果树应为：
50 \ 60 \ 90
我想到了两种方法： A1： node * deleteTree（node * A，node * B）； 取树B的根。从树A删除此节点（通过常规BSt删除方法）。接下来，将问题分为两部分- B的左子树和B的右子树。对于每个子树，递归。对于左子树，占据已删除节点的节点应作为树A的根。对于右子树，已删除节点的有序后继服务器应作为树A的根。
A2：另一种方法有点怪异。我找到了树A的有序遍历和预排序遍历。使用二进制搜索和递归查找和删除树B中的所有节点（我们不修改前序）。最后，从inorder（剩余）和preorder（不变）重建bst。
问题A：找到有效的BST方法。 问题B：找到任何二叉树（不仅仅是BST）的有效方法。
我认为两棵树是平衡的。
void deleteTree(node* A, node* B) { if(A == NULL || B == NULL) return; if(A->data == B->data) { deleteTree(A->left, B->left); deleteTree(A->right, B->right); removeNode(A); // Normal BST remove } else if(A->data > B->data) { Node* right = B->right; B->right = NULL; deleteTree(A->left, B); deleteTree(A, right); } else // (A->data < B->data) { Node* left = B->left; B->left = NULL; deleteTree(A->right, B); deleteTree(A, left); } }
时间复杂度：
T(N) = 2 * T(N / 2) + O(1)
因此，根据主定理，总体复杂度为 O（N） 。空间复杂度为 O（1） 。一个缺点是我破坏了B。
PS：我手头没有BST实现，因此我无法为您测试代码。但是我认为这个想法是正确的。
将哈希表用于一棵树，然后遍历另一棵树。您将获得 O（N） 的时间和空间复杂度。
