树中两个节点之间的最大距离

Question

我正在尝试找出树中两个节点之间的最大距离。这是我的程序：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;


public class distance {

    static ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
    static ArrayList<Integer> visited=new ArrayList<Integer>();
    static ArrayList<Integer> depth=new ArrayList<Integer>();
    static ArrayList<Integer> depth1=new ArrayList<Integer>();
    static int sum=-1;
    static boolean[] arr;
    static int root=0;


    public static void main(String args[])
    {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();     //no of nodes

        for(int i=0;i<=n;i++)   
        {
            list.add(new ArrayList<Integer>());
        }
        int a;
        int b;
        for(int i=0;i<n-1;i++)  //populating the adjacency list
        {
            a=in.nextInt();
            b=in.nextInt();
            list.get(a).add(b);
            list.get(b).add(a);
        }

        arr=new boolean[n+1];

        dfs(root);

        int final_sum=0;
        Collections.sort(depth1);
        System.out.println(depth1.get(depth1.size()-1)+depth1.get(depth1.size()-2));

        }
    public static void dfs(int n)
    {   
        arr[n]=true;
        visited.add(n);
        sum=sum+1;

        if(list.get(n).size()==1)
        {   
            depth.add(sum); //add the depth to the arraylist when we reach a leaf node.Note the this will not run if the root node has only one child but I've ignored the case.
        }
        if(n==root)
        {
            for(int j=0;j<list.get(0).size();j++)
            {   
                dfs(list.get(0).get(j)); //recursion on each child of the root node
                sum=0;
                Collections.sort(depth);
                depth1.add(depth.get(depth.size()-1));
                depth.clear();
            }

        }
        else
        {
            for(int l:list.get(n))
            if(!arr[l]==true)
            {
                dfs(l);
                sum--;

            }
        }


    }

}

程序好像是运行；但没有显示某些测试用例的正确输出。我采取的方法是：

求根节点的children个数（我一直把根节点取0）
求每个sub-tree的最大深度（根节点有多少children就有多少sub-tree）。
将每个 sub-tree 的最大深度存储在一个 ArrayList 中，对其进行排序并打印最后两个值的总和。

谁能指出我程序中的错误？

Answer 1

首先是算法的错误。您假设两个节点之间的最大距离始终包含根节点，但这并不总是成立。

这是一个例子：

最长路径的节点用红色标记。最长路径的长度为 6 并包含 7 个节点，而您的算法仅查找通过根的路径，因此打印 5 作为答案。

树中两个节点之间的最大距离

Maximum distance between two nodes in a tree

java

algorithm

tree