题解 | #多叉树的直径#

import java.util.*;

public class Solution {
    /**
     * 树的直径
     *
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @param maxSum 记录当前最大路径
     * @param visited 记录图遍历过的结点
     * @return int整型
     */
    int maxSum;
    int[] visited;

    public int solve(int n, ArrayList<Interval> Tree_edge, ArrayList<Integer> Edge_value) {
        // write code here
        maxSum = 0;
        visited = new int[n];
        // 将多叉树转换为有权无向图，存放在双层map
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int i = 0; i < Tree_edge.size(); i++) {
            Map<Integer, Integer> child1 = graph.getOrDefault(Tree_edge.get(i).start, new HashMap<>());
            child1.put(Tree_edge.get(i).end, Edge_value.get(i));
            graph.put(Tree_edge.get(i).start, child1);
            Map<Integer, Integer> child2 = graph.getOrDefault(Tree_edge.get(i).start, new HashMap<>());
            child2.put(Tree_edge.get(i).end, Edge_value.get(i));
            graph.put(Tree_edge.get(i).end, child2);
        }
        // 既然是树结构，无论从以哪个结点作为根结点并从其出发，都可以遍历到所有结点
        maxGain(graph, 0);
        return maxSum;
    }

    /***
     *
     * @param graph
     * @param root 根结点的序号
     * @return 经过root的最大路径
     */
    public int maxGain(Map<Integer, Map<Integer, Integer>> graph, int root) {
        visited[root] = 1;
        int maxChildGain = 0;
        int secondMaxChildGain = 0;
        Map<Integer, Integer> childMap = graph.get(root);
        if (childMap == null || childMap.size() == 0) {
            return 0;
        }
        int child, path;
        for (Map.Entry<Integer, Integer> kv : childMap.entrySet()) {
            child = kv.getKey();
            path = kv.getValue();
            path += maxGain(graph, child);
            if (path > maxChildGain) {
                secondMaxChildGain = maxChildGain;
                maxChildGain = path;
            } else if (path > secondMaxChildGain) {
                secondMaxChildGain = path;
            }
        }
        /**
         * 题目中所求的最大路径，必然会经过某个子树的根结点。
         * 所以在遍历过程中，对于每个结点，都求一次以该结点为根的子树，经过根结点的最大路径
         * 与maxSum进行对比即可求出最大路径
         */
        maxSum = Math.max(maxSum, maxChildGain + secondMaxChildGain);
        visited[root] = 0;
        return maxChildGain;
    }
}