algorithm - 二叉搜索树中的删除

Question

I have been given two binary search trees. For example, A and B. Next, I was asked to delete the tree B from the tree A.

通过删除，我的意思是从 A 中删除 B 中存在的所有节点。注意:B 不一定是 A 的子树。

例如:
答:

      50   
     / \  
    10  75  
   /   / \  
  1   60   90                 

乙:

     10
     / \
    1   75

结果树应该是:

     50
       \
        60
         \ 
          90

我想到了两种方法:
A1:
节点* deleteTree(节点* A, 节点* B) ;
取树 B 的根。从树 A 中删除该节点(通过正常的 BSt 删除方法)。接下来将问题分为两部分 - 对于 B 的左子树和 B 的右子树。对于每个子树，递归。对于左子树，占据被删除节点的节点作为树A的根。对于右子树，删除节点的中序后继作为树A的根。

A2:另一种方法有点奇怪。我找到树 A 的中序和前序遍历。使用二进制搜索和递归查找并删除树 B 中的所有节点(我们不修改前序)。最后从中序(剩余)和前序(不变)重构我们的 bst。

问题 A:找到 BST 的有效方法。
问题 B:为任何二叉树(不仅仅是 BST)找到一种有效的方法。

Answer 1

问题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) 的时间和空间复杂度。