3.2.31

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

解答

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

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

代码

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 库

上一题 下一题