-1

在 BST 中找到每个级别的最大元素。？

[1] In O(n) time and O(1) space
[2] In O(logn) time and O(n) space

编辑：@Imposter 发布的解决方案适用于 [1] 这是 [1] 的解决方案

private int level = 0;
private int VisitedLevels = -1;

public void findLargestByLevel(AvlNode root)
{
    if(root == null) return;

    else
    {
        if(level > VisitedLevels)
        {
            System.out.println(root.data + " @ Level = " + level);
            VisitedLevels++;
        }
        level++;

        findLargestByLevel(root.right);
        findLargestByLevel(root.left);

        level--;
    }
}

但我仍然无法为 [2] 找到解决方案

我想到的方法：如果我们对树进行预处理并将其展平，就像树的序列化一样，

                 100
             50         200
         20      75

#L0, 100, #L1, 50, 200, #L2, 20, 75, #L3

其中#L 是级别的标记：

那么我们可以在 O(1) 时间内轻松回答最高和最低级别的查询，此外，如果树被修改，我们可以在 LogN 时间内从序列化数据中执行插入和删除。请为 [2] 推荐某人，虽然在我看来 zit 看起来不可能实现 [2] 但我想听听其他人的建议

4

2 回答 2

6

如果 BST 是 Full BST，那么它可以在 log(N) 时间内完成，因为您需要做的就是一直向右遍历（因为右侧的元素总是比左侧大。）如果它不是完整的 BST然后我们必须遍历所有元素，因为我们不确定右子树的高度总是大于左子树。

示例：如果右子树有两层而左子树有三层，那么使用上述方法我们可以打印最大值直到两层，但我们错过了右子树中不存在的第三层。

因此，如果不是 Full BST，时间复杂度将是最小的 O(n)，如果没有给出额外的空间，则可能会更高。

如果你做 BFS，它只需要 O(n) 时间复杂度和 O(n) 空间复杂度。如果你想要它使用 DFS 那么下面的算法将帮助你 O(n) 时间复杂度和 O(h) 其中 h 是树的高度。

取全局变量计数器，它指示到目前为止遍历时的最大级别数。

当你递归调用左子树增量L时，取两个变量L和R

同样，当您对右子树增量R进行递归调用时。

找到每个节点的L和R的最大值，它给出了 level number 。

当节点的 max( L,R )有增量时，如果计数器小于 max( L,R )，则使用计数器检查它，然后分配内存并初始化为零并递增计数器。（这意味着我们实际上是在创建树中每个级别的变量）。

在遍历时，我们将每次检查高度或级别变量，并将其与正在考虑的当前节点进行比较，如果当前节点大于级别变量，则使用正在考虑的节点更新级别变量。

遍历后打印高度或水平变量。

于 2012-09-21T06:45:38.267 回答
-1

[1] 这可以通过遍历每个级别并记录最大值来迭代地完成。这可以通过一个简单的 BFS 来完成（假设您不计算存储中的递归级别变量）。例如。用简单队列替换的递归将花费超过 O(1) 的存储空间，在这种情况下，这对我来说似乎是不可能的，除非节点是按级别排序的。

[2] 二叉树具有右孩子大于左孩子的属性，因此如果您每次只遍历最右边的孩子（除非它不存在，则取左孩子），您可以获得 log(n) 时间的最大值。我不确定它是否需要 O(n) 存储。

于 2012-09-21T05:29:26.443 回答