解锁一道会员题—LeetCode1245

先由一道easy题入手 LeetCode 543

二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 对于每个节点，直径即其左子树和右子树的深度的和，而对整个树，这些节点的直径中的最大值即是树的直径。 方法：采用dfs，建立辅助函数，函数返回值为以当前root节点为根节点的树的深度。

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans;
    }
    //遍历每个节点,此方法返回root为根节点的树的深度
    public int depth(TreeNode root){
        if(root == null) return 0;
        int l = depth(root.left);//根节点为root的左子树的深度
        int r = depth(root.right);//根节点为root的右子树的深度
        ans = Math.max(ans, l + r);//更新树的直径
        return Math.max(l, r) + 1；
    }
}

有了上面的铺垫，那看一下主角题目： 虽然是树，但已经转化为图的题。 任意一个节点的最大直径是从自身出发的所有路径中最长两条路径长度的和。 依然采用dfs，则辅助函数返回值为以当前节点root（父节点parent）为起点的路径的最大值。函数中需要维护一个最大长路径max1，和一个次长路径max2。并维护一个res，不断与max1+max2 进行比较，求最大值即为最长直径。

继续思考： 如果无向图中的路径有值呢？

题目中给出的是edges关系。还需要建立一个新的Node类，和一个List<Node>[] 邻接表记录节点之间的关系。

辅助函数依然返回的是当前节点root为起点的一条路径的最长长度。 代码如下：

import java.util.*;
/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */
public class Solution {
   class Node{  // 邻接点结构
        int id, dist; //id表示节点编号，dist表示距离
        public Node(){}
        public Node(int id, int dist){
            this.id = id;
            this.dist = dist;
        }
    }
    int res = 0;
    List<Node>[] g; // 保存邻接点
 
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        g = new List[n];
        for (int i = 0; i < n; ++i){
            g[i] = new LinkedList<>();//每个节点的邻接点和距离值
        }
 
        for (int i = 0; i < n - 1; ++i){
            int x = Tree_edge[i].start, y = Tree_edge[i].end;
            g[x].add(new Node(y, Edge_value[i]));
            g[y].add(new Node(x, Edge_value[i]));
 //g[0]:Node(1,3) g[1]:Node(0,3),Node(2,2),Node(5,4) g[2]:Node(1,2),Node(3,1),Node(4,5) g[3]:Node(2,1) g4:Node(2,5) g[5]:Node(1,4)
        }
        dfs(0, -1);
        return res;
    }
    //返回当前节点root（父节点为parent）为起点的路径的最大值
    public int dfs(int root, int parent){
         List<Node> list  = g[root];
        int max1 = 0; // 以当前节点为起点的一条最大路径长度
        int max2 = 0; // 以当前节点为起点的一条次大路径长度
        for(Node next : list){
            //防止走回头路
            if(next.id != parent){
                int max = dfs(next.id, root) + next.dist;
                if(max >= max1){
                    max2 = max1;
                    max1 = max;
                }else if(max >= max2){
                    max2 = max;
                }
                // max1+max2得到当前节点最大边长,与返回结果比较，更新最大值
                res = Math.max(res, max1 + max2);
            }
        }
        // 返回当前节点一条路径的最大长度
        return max1;
    }        
}