3.2.31

3.2.31 #

解答 #

本题在原书后续印刷中已删除，这里仍然采用中文版的题目。

注意这个题并没有递归的要求，直接广度优先搜索即可，随时记录和检查已找到的键。

代码 #

protected static bool HasNoDuplicates(Node x)
{
    var keys = new List<TKey>();    // 也可以用 HashSet 之类的数据结构提高效率。
    var queue = new Queue<Node>();
    queue.Enqueue(x);
    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        if (node == null)
        {
            continue;
        }

        if (keys.Contains(node.Key))
        {
            return false;
        }
        keys.Add(node.Key);
        queue.Enqueue(node.Left);
        queue.Enqueue(node.Right);
    }

    return true;
}

另请参阅 #

BinarySearchTree 库