1

Im trying to put to an array the deepest path on a BST using a recursive algorithm, and im getting several difficulties... because the only thing that i get is the size of the longest path(equivalent to the height), and i cant put in the array the values regarding to the height of the BST...

Any help?

Sorry, I didn't expose the problem in the entire way. The only thing that I know to do this algorithm is this signature:

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

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

(I can use aux methods)

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 回答