3.2.42

上次更新:2019-12-08
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

按照题意实现即可,关键点有两个:

一是选择前驱的实现方式,只要选择左子树中的最大结点即可。

if (_random.NextDouble() < 0.5)
{
    x = Min(t.Right);
    x.Right = DeleteMin(t.Right);
    x.Left = t.Left;
}
else
{
    x = Max(t.Left);
    x.Left = DeleteMax(t.Left);
    x.Right = t.Right;
}

二是内部路径长度的计算方式,需要用层序遍历把所有结点的深度加起来。

var internalPath = 0;
var nowLayer = new Queue<Node>();
var nextLayer = new Queue<Node>();
nextLayer.Enqueue(root);

var depth = 0;
while (nextLayer.Count > 0)
{
    var temp = nowLayer;
    nowLayer = nextLayer;
    nextLayer = temp;

    while (nowLayer.Count > 0)
    {
        var node = nowLayer.Dequeue();
        if (node.Left != null)
        {
            nextLayer.Enqueue(node.Left);
        }

        if (node.Right != null)
        {
            nextLayer.Enqueue(node.Right);
        }

        internalPath += depth;
    }

    depth++;
}

return internalPath;

结果如下:

另请参阅

BinarySearchTree 库

上一题 下一题