3.2.25

3.2.25 #

解答 #

官方实现：https://algs4.cs.princeton.edu/32bst/PerfectBalance.java.html

先排序，然后视其为中序序列，每次取中间的键作为根结点，左半数组是左子树，右半数组是右子树，递归构造。

private Node BuildTree(KeyValuePair<TKey, TValue>[] init, int lo, int hi)// init is sorted
{
    if (lo > hi)
    {
        return null;
    }

    var mid = (hi - lo) / 2 + lo;
    var current = new Node(init[mid].Key, init[mid].Value, 1);
    current.Left = BuildTree(init, lo, mid - 1);
    current.Right = BuildTree(init, mid + 1, hi);
    if (current.Left != null)
    {
        current.Size += current.Left.Size;
    }

    if (current.Right != null)
    {
        current.Size += current.Right.Size;
    }
    return current;
}

另请参阅 #

BinarySearchTree 库