在二叉树中删除

Question

我得到了两个二进位搜索树。例如，A和B。接下来，我被要求从树A中删除树B。

删除的意思是从A中删除B中的所有节点。注意:B不一定是A的一个子树。

例：

答：

50 / \ 10 75 / / \ 1 60 90

B：

10 / \ 1 75

由此产生的树应该是：

50 \ 60 \ 90

我想到了两种方法：

A1：

节点*deleteTree(节点* A，节点* B)；

取树根B。从树A中删除此节点(通过正常的BSt删除方法)。接下来，将问题分为两部分: B的左子树和B的右子树，每个子树都是recurse。对于左子树，占据被删除节点的节点应作为树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)。

Answer 2

在我看来，为什么不按顺序遍历b。然后，直到数组不为空为止，对数组索引的值执行一个常规的删除。遍历是O(n)，每个索引的删除将是O(logn)。总之，这个操作将是O(nlogn)。