0

面接の準備をしようとしていますが、次の問題に遭遇しました。

ツリー構造のルートが与えられます。メソッド getChildren() は、その親のすべての子を持つ Node[] 配列を返します。問題は、特定のノード x がツリーに存在するかどうかを確認することです。反復と再帰の両方でこれを行うにはどうすればよいですか? 誰かが疑似コードを提供してくれると助かります。深さ優先検索を実行できることは理解していますが、各要素が任意の数の子ノードを持つことができるツリーに対して実行する方法がわかりません。

4

1 に答える 1

1

あなたの再帰的アプローチは次のようになります

FUNCTION exists(Node target, Node root):

    Node[] children = root.getChildren()

    IF children NOT null:  //if there are children go on to visit each one
        FOR child IN children:
            IF exists(target,child):
                RETURN true
    ELSE: //the base case, when 'root' has no children check if it's the value
        RETURN root.value == target

    RETURN false //will only be reached from the first call to exists() if there hasn't been a match already

Python では、これは次のようになります。

def exists(target,root):
    if isinstance(root,list):
        for child in root:
            if exists(target,child):
                return True
    else:
        return target == root
    return False

いくつかの例：

print exists(2,[[[2]]])
print exists(2,[[1,4,5,[2]]])
print exists(2,[0,0,0,[0,[1,1,1]]])
>>> 
True
True
False

Pythonでの反復は次のようになります

def existsNR(value,root):
    visitstack = [child for child in root]
    while visitstack:
        node = visitstack.pop()
        if isinstance(node,list):
            visitstack += node
        else:
            if node == value:
                return True
    return False

この背後にあるロジックは、「ルート」の最初の子のそれぞれを調べ、子を持つ子ごとに、子をスタックにプッシュし、それらの子 (子) の「親」を削除することです。これらの子をチェックし、同様の方法でそれらを追加します...子を持たないものに到達するまで、その時点で等しいかどうかをチェックします。

于 2013-09-29T05:25:32.017 に答える