1

再帰アルゴリズムを使用してBSTの最も深いパスを配列に入れようとしていますが、いくつかの問題が発生しています...取得できる唯一のものは最長パスのサイズ(高さに相当)であり、できないためですBSTの高さに関する値を配列に入れます...

何か助けはありますか？

申し訳ありませんが、問題を完全に公開しませんでした。このアルゴリズムを実行するために私が知っている唯一のことは、次の署名です。

//each node has 3 references : value, left and right

private int [] deepestPath(Node root){ ...}

(補助メソッドを使用できます)

4

2 に答える 2

1

ノードをツールとして使用して、最も深いパスを再構築してみてください

問題は、ツリーをトラバースするときに実際のノードを格納する方法がないことです。必要なのは、最も深いと思われる葉に向かう途中で訪れたノードを「記憶」する方法です。

BST がノードで表されている場合は、各子にその親への参照を格納することを検討してください。そうすれば、最も深いリーフに到達したときに、ルートに戻るパスを再帰的に再構築できます (注: パスは逆順になります)。そのようです：

if (isDeepest(node)) { // Once you find the deepest node...
  return reconstructPath(node); // ...reconstruct the path that took you there.
}

...

// reconstructPath is a method that takes a node (the deepest leaf) as 
// an argument and returns an array of the nodes from that node to the root.
private Array reconstructPath(Node node) {
  Array deepestPath = new Array();
  while(node.parent != node) { // Go up until you reach the root, which will be itself.
    deepestPath.add(node); // Add the node to end of the Array
    node = node.parent; // Go up one level to the parent of the node
  }
  deepestPath.reverse(); // reverse the order so it goes root->leaf
  return deepestPath;
}

ノードを使用したくない場合、これを行う方法は他にもありますが、頭の中で問題を視覚化する簡単な方法です。

于 2009-07-24T22:29:36.390 に答える
0

親参照あり

親への参照を持つように各ノードを設定すると、最も深いノードを見つけて、そこから親をたどってツリーのルートに戻ることができます。parentNodeこれは、各ノードに追加の参照変数を追加することを犠牲にして行う最も簡単な方法です。

# Iterate through parents to trace the path in reverse.
node = deepestNode(tree)

while node.parent != None:
    node = node.parent

親参照なし

親参照がない場合は、ツリーを再帰するときに、ツリーのルートから「現在の」ノードまでのパスを追跡できます。ボトムアウトするたびに、パスが以前の「これまでの最長パス」よりも長い場合は、そのパスを「これまでの最長パス」として保存します。事実上、これはコール スタックを明示的にすることを意味します。

Pythonっぽいコードは次のとおりです。

# Public function. Sets up globals and then calls helper.
def deepestPath(tree):
    global longestPath, currentPath

    # Reset for a new search.
    longestPath = []
    currentPath = []

    _deepestPath(tree.root)

    return longestPath

# Helper function that does the real work.    
def _deepestPath(node):
    global longestPath, currentPath

    currentPath.append(node)

    # No children, we've bottomed out.
    if not node.left and not node.right:
        if currentPath.length > longestPath.length:
            # Save a copy of the current path.
            longestPath = list(currentPath)

    # Recurse into children.
    else:
        if node.left:  _deepestPath(node.left)
        if node.right: _deepestPath(node.right)

    currentPath.pop(node)
于 2009-07-24T22:31:11.537 に答える