0

インタビューの準備をしているので、演習として、二分木がBSTであるかどうかを確認するアルゴリズムを実装しました。

    public static bool CheckBST(this Node root)
    {
        if (root == null) throw new ArgumentException("root");
        Node previous = null;
        foreach (var node in GetNodes(root))
        {
            if (previous != null && node.value <= previous.value)
            {
                return false;
            }
            previous = node;
        }
        return true;
    }

    private static IEnumerable<Node> GetNodes(Node root)
    {
        if (root.left != null)
        {
            foreach (var node in GetNodes(root.left))
            {
                yield return node;
            }
        }
        yield return root;
        if (root.right != null)
        {
            foreach (var node in GetNodes(root.right))
            {
                yield return node;
            }
        }
    }

foreachループを取り除くことができますか（まだ再帰とyieldを使用しています）？

4

1 に答える 1

3

いいえ、残念ながら、これを達成する方法はありません。ノーマルも混じり合いも許されない
ということはありません。yield return many GetNodes(...);yield returnreturn

ただし、LINQ を使用して目的の結果 (遅延実行) を実現できます。

private static IEnumerable<Node> GetNodes(Node root)
{
    var result = Enumerable.Empty<Node>();

    if (root.left != null)
        result = result.Concat(GetNodes(root.left));

    result = result.Concat(new [] { root });

    if (root.right != null)
        result = result.Concat(GetNodes(root.right));

    return result;
}

これがあなたが現在持っているものよりも優れているかどうかは議論の余地があります.

于 2012-12-05T14:28:03.480 に答える