5

最近のインタビューで、次の質問を受けました。ノードの値として整数が含まれる BST が与えられた場合、ノードが整数 X (最小) と Y (最大) の間に収まるすべてのサブツリーを検索します。ここで、X<Y です。これらのサブツリーは互いにオーバーラップできません。

この問題のバリエーションを解決しました。たとえば、特定の範囲にある BST のキーを出力します。しかし、非常に特定の制約を満たすメイン グラフ/ツリーのすべての接続されたサブグラフを見つける必要があるため、これを理解できませんでした。ポインター/ヘルプ/疑似コードは大歓迎です。

追記 -

  1. この問題は、node のデータ構造を、左ポインター、右ポインター、および整数値を持つものとして定義していました。ノードをマークする方法がありませんでした。
  2. これをJavaで解決するように依頼されました。
  3. サブツリー/サブグラフと言ったとき、ばらばらのノードのリストではなく、接続されたノードのセットを意味しました。混乱させて申し訳ありません。
4

4 に答える 4

1

範囲検索を行う場合、一般的な言語で書かれた範囲の主力関数は次のようになります。

function range(node, results, X, Y) 
{
    if node is null then return
    if node.key is in [X, Y] then results.add(node.key)
    if node.key < Y then range(node.right, results, X, Y)
    if node.key > X then range(node.left, results, X, Y)
}

サブツリーのバージョンの問題については、キーの代わりにサブツリーのルート ノードを保存し、サブツリーにいるかどうかを追跡する必要があります。後者は、範囲呼び出しでサブツリーごとの親を渡すことで解決できます。これは、新しい構造の作成にも必要です。欲しい機能は以下。ご覧のとおり、主な変更点は 1 つの追加の引数とnode.key in [X, Y]分岐です。

function range_subtrees(node, parent, results, X, Y) 
{
    if node is null then return

    node_clone = null 

    if node.key is in [X, Y] then 
        node_clone = node.clone()
        if parent is null then 
            results.add(node_clone)
        else
            parent.add_child(node_clone)

    if node.key < Y then range_subtrees(node.right, node_clone, results, X, Y)
    if node.key > X then range_subtrees(node.left, node_clone, results, X, Y)
}

これにより、各サブツリーが元のツリー構造のコピーであるサブツリー ルート ノードのコレクションが作成されます。

于 2015-06-28T10:15:43.027 に答える