查找树形结构中最长路径

Question

我有一个树形结构，看起来像以下这样：

Tree {
   Node root;
}

Node {
   List children;
}

我正在尝试编写一个方法来返回最长路径的长度。我看到了一些关于二叉树的解决方案，但是每个节点可以有无限数量的子节点，这就是我的问题所在。

- user2998228

---

1. 请具体说明问题类型。
2. 除了上述提到的（类似）模板之外，您尝试过什么？

- Prateek

Answer 1

我应该像这样做

int getLongestPathLength(Node node) {
    if(node == null) return 0;
    int max = 0;
    for(Node child : node.children){
        max = Math.max(getLongestPathLength(child),max);
    }
    return 1+max;
} 

- Alessio

Answer 2

看起来你正在寻找的是根节点的高度。你可以在这里看到计算它的基本算法（类似于先前答案中给出的算法）：http://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-08.html。

- JRe