在二叉搜索树中删除

问题A

我认为两棵树是平衡的。

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实现，因此我无法为您测试代码。但是我认为这个想法是正确的。

问题B

将哈希表用于一棵树，然后遍历另一棵树。您将获得 O（N） 的时间和空间复杂度。