给的多叉树, 找这颗树里面最长的路径长度
解法就是在子树里面找最大的两个（或一个，如果只有一个子树的话）高度加起来。
对于每一个treenode, 维护它的最高的高度和第二高的高度，经过该点的最大路径就是： 最高高度+第二高高度，然后return 最高高度
package fbPractise;
import java.util.*;
class TreeNode {
int val;
List<TreeNode> children;
public TreeNode(int value) {
this.val = value;
this.children = new ArrayList<TreeNode>();
}
}
public class LongestPathInTree {
static int maxLen = 0;
public static int findLongestPath(TreeNode node) {
findMaxPath(node);
return maxLen;
}
public static int findMaxPath(TreeNode node) {
if (node == null) return 0;
int heightest1 = 0;
int heightest2 = 0;
for (TreeNode child : node.children) {
int childHeight = findMaxPath(child);
if (childHeight > heightest1) {
heightest2 = heightest1;
heightest1 = childHeight;
}
else if (childHeight > heightest2) {
heightest2 = childHeight;
}
}
maxLen = Math.max(maxLen, 1 + heightest1 + heightest2);
return 1 + heightest1;
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
node1.children.add(node2);
node1.children.add(node3);
node2.children.add(node4);
node2.children.add(node5);
node5.children.add(node6);
int res = findLongestPath(node1);
System.out.println(res);
}
}