我正在尝试提出一种从二叉树/二叉搜索树中删除重复项的算法。到目前为止，我能想到的最好的是
Store Inorder traversal of tree in an array.
If the tree has no ordering, sort the array.
remove duplicates from the array and reconstruct the binary tree.
我们是否需要存储树的前序遍历以及重建树？
这使得复杂度为 O(n log n ) 时间和 O(n) 空间。我们能做得更好吗？伪代码/代码示例将不胜感激
编辑 1:假设二叉树的结构由以下对象给出
public class Node
{
int data;
Node right;
Node left;
// getters and setters for the left and right nodes
}
最佳答案
删除二叉搜索树的重复算法:
开始树上漫步(按顺序/前/后顺序)
在每个节点上，对以该节点为根的子树进行二分搜索，以查找存储在该节点中的键值。
如果在树下找到键值，调用 delete(key) 并重新开始第 2 步(可能有多个重复项)。
重复步骤 2，直到在子树中找不到键。然后回到步骤1
时间复杂度 - O(nlogn)(对每个 n 元素进行二进制搜索，这需要 logn 时间)
空间复杂度 - O(logn)(递归中使用的堆栈空间)
关于algorithm - 从二叉树中删除重复项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20013384/