考虑有一个BST，它有重复的元素 . 您必须从树中删除所有重复的元素 . 当找到相等的密钥时在BST中的插入是随机的，即，当在树中插入密钥时，如果所述密钥已经存在，则可以将密钥插入左子树或右子树中，但仍然遵循BST的基本属性 . 因此，任何节点的左子树上的所有键都小于或等于节点，并且任何节点的右子树上的键大于或等于节点 . 你会如何删除所有重复的元素 .
请注意，如果一个密钥说例如15出现在整个树中三次，我们不会删除所有三个实例，但只删除两个，无论哪两个都没关系 .
有一种以PreOrder方式遍历树的强力方法 . 然后查找并删除左侧和右侧子树上的元素，这些元素的键等于所述节点 .
有没有更好的方法来解决这个问题？
1 回答
您提到的暴力方法具有
O(n^2)的最坏情况复杂性 .实现更好复杂性的一种方法是使用
hash-table. 您可以在BST上执行遍历并将每个节点的计数存储在哈希表中 . 然后，再做一次（以任何适合你的方式）并删除计数大于1的节点 . 假设树是 balancer 的，该方法具有改进的O(n*logn)的复杂性 .