algorithm - 二叉搜索树中出现频率最高的元素

Question

我们如何才能找到 BST 中出现频率最高的元素？我想过使用哈希映射来实现它。有什么简单的方法吗？

Answer 1

这个问题等同于在排序数组中查找最频繁的元素——同样的算法适用：

• 从零开始计数器
• 在当前元素等于前一个元素时增加计数器
• 当您找到不同的元素时，将计数器与当前最佳运行进行比较；必要时更换
• 继续下一个元素

唯一的区别是，不是使用循环遍历数组，而是使用递归函数进行树遍历。在这两种情况下，算法在树中元素的数量上都是线性的。如果树是平衡的，则算法需要O(LogN)调用堆栈上的空间。

Answer 2

它可以通过多种方式完成 -

1. 进行中序遍历。这将为您提供元素的排序列表。进行线性遍历以找到重复次数最多的元素。time O(n) space O(n)
2. 像你说的哈希表。执行 BST 的任何DFS 遍历。将每个元素插入到计数设置为 1 的哈希表中。如果元素已经存在，则增加 count+1。然后遍历哈希表找出频繁出现的元素。最坏的时间O(n)和空间O(n)，但在实践中，如果数据集有很多重复，这种方法应该占用更少的空间。

Answer 3

这是最干净的方法：

• 初始化一个哈希映射，它将一个值映射到它的出现次数。
• 按顺序迭代 BST：
  • 哈希[node.value] += 1

---

您可以就地完成（O(1)额外的内存复杂性）：

保留 2 个O(1)变量表示最大出现次数和元素，按顺序迭代树，保证它以递增的方式，并更新元素的最大出现次数：

curmax = 0
maxnode = null
for each node in BST.inorder():
    if next.value == node.value:
        max ++
    else:
        max = 1
    if max > curmax:
        curmax  = max
        maxnode = node

Answer 4

我们可以如上所述使用修改后的中序遍历并跟踪前一个元素。

TreeNode prev = null;
int count = 1, max = 0;
List<Integer> list = new ArrayList<>();


private void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    if (prev != null) {
        if (root.val == prev.val)
            count++;
        else
            count = 1;
    }
    if (count > max) {
        max = count;
        list.clear();
        list.add(root.val);
    } else if (count == max) {
        list.add(root.val);
    }
    prev = root;
    inorder(root.right);
}

由于中序遍历为我们提供了升序的元素，这种技术很有用，这里的列表将包含这些元素。