在BST中查找每个级别的最大元素

Question

找到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],但我想听听别人的建议

Answer 1

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

示例:如果右子树有两个级别,左子树有三个级别,那么使用上面的方法我们可以打印最大值直到两个级别但我们错过了右子树中不存在的第三级别.

因此,如果不是全BST,时间复杂度将是最小O(n),如果没有给出额外空间,则时间复杂度可能更高.

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

获取全局变量计数器,该计数器指示到目前为止的最大级别数.

在对左子树增量L进行递归调用时,取两个变量L和R.

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

找到每个节点的最大L和R,给出级别编号.

当遍历时节点的最大值(L,R)增加时,如果计数器小于max(L,R),则用计数器检查此值,然后分配存储器并初始化为零并增加计数器.(这意味着我们实际上正在创建树中每个级别的变量).

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

遍历打印高度或级别变量后.