0

我在实现这一点时遇到了一些麻烦。我知道我需要进行深度优先搜索以找到最深的路径，该路径将给出子字符串的索引。在实施 dfs 时遇到一些问题，可能是我的理解不佳：

int getDeepestPath(TreeNode node)
{
    int maxDistance = 0;
    TreeNode maxNode;
    if(node == null) return 0;
    System.out.println(node.getSuffix());
    if(node.getSuffix() != -1) return 0;  
    else
    {
        TreeNode nextNode = node.getChild();
        while(true)
        {
            int distance = 0;
            if(nextNode != null)
            {
                distance = (nextNode.getRightLabel() -nextNode.getLeftLabel()) + 1;
                System.out.println(distance + " distance");
                distance = getDeepestPath(nextNode,t2Info) + distance;
                if(distance > maxDistance) maxDistance = distance;
                nextNode = nextNode.getSibling();
            }
            else break;
        }
    }

    System.out.println(maxDistance);
    return maxDistance;
}

最终的目的是存储最深的节点和路径的长度——我现在只是想打印路径的长度。

谢谢

4

2 回答 2

0

为什么不直接使用堆栈实现 DFS 并将变量添加到node被调用的visited. 每次将节点推送到堆栈时，标记visited = true. 伪代码

root.visited = true;
root.push()
while(Stack.isEmpty()) {
  if(!root.next.visited) {
    root.next.push()
  }
}

实现查找叶子、转到下一个分支和弹出的逻辑。这是一个通用逻辑，如果你有一个二叉树，你可以改变它，让它更简单，只有两个孩子（左和右）

于 2013-02-14T20:05:49.237 回答
0

你的假设是错误的。

在后缀树中，每个节点都应该包含一个在该节点上终止的字符串的键列表。如果列表为空，则该节点没有定义任何字符串。无需在树中找到长路径。例如，如果树中有三个字符串，“app”（1）、“apple”（2）和（5）以及“apple pie”（3），那么树将如下所示：

"app" 1  
  |  
"le" 2, 5  
  |  
" pie" 3
于 2013-02-14T21:56:34.330 回答