树的直径

题目描述

https://leetcode.cn/problems/tree-diameter

给你这棵「无向树」，请你测算并返回它的「直径」：这棵树上最长简单路径的边数。

我们用一个由所有「边」组成的数组 edges 来表示一棵无向树，其中 edges[i] = [u, v] 表示节点 u 和 v 之间的双向边。

树上的节点都已经用 {0, 1, ..., edges.length} 中的数做了标记，每个节点上的标记都是独一无二的。

示例 1：

输入：edges = [[0,1],[0,2]]
输出：2
解释：
这棵树上最长的路径是 1 - 0 - 2，边数为 2。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
输出：4
解释： 
这棵树上最长的路径是 3 - 2 - 1 - 4 - 5，边数为 4。

提示：

0 <= edges.length < 10^4
edges[i][0] != edges[i][1]
0 <= edges[i][j] <= edges.length
edges 会形成一棵无向树

思路：回溯法(超时)

回溯法试探，每一个可能，计算最大长度。会超时

csharp

public class Solution {

    int diameter=0;
    bool[] used;

    private void dfs(int[][] edges, int ingress, int d){
        diameter = Math.Max(diameter,d);
        for(int i=0; i<edges.Length; i++){
            if((edges[i][0] == ingress || edges[i][1] == ingress) && !used[i]){
                used[i] = true;
                if(edges[i][0] == ingress){
                    dfs(edges, edges[i][1],d+1);
                }
                else{
                    dfs(edges, edges[i][0],d+1);
                }
                used[i] = false;
            }
        }
    }

    public int TreeDiameter(int[][] edges) {
        int n = edges.Length;
        used = new bool[n];
        for(int i=0; i<n; i++){
            dfs(edges,i,0);
        }
        return diameter;
    }

}

思路：官方

没看懂

csharp

public class Solution {
    int res = 0;

    List<IList<int>> map = new List<IList<int>>();
    bool[] used  ;

    private int dfs(int index){
        used[index] = true;
        IList<int> list = map[index];
        int max1 = 0;
        int max2 = 0;
        for(int i=0; i<list.Count; i++){
            int next = list[i];
            if(!used[next]){
                int num = dfs(next);
                if(num > max1){
                    max2 = max1;
                    max1 = num;
                }
                else if(num > max2){
                    max2 = num;
                }
            }
        }
        res = Math.Max(res,max1+max2);
        return Math.Max(max1,max2)+1;
    }

    public int TreeDiameter(int[][] edges) {
        int n = edges.Length;
        for(int i=0; i < n+1; i++){
            map.Add(new List<int>());
        }
        for(int i=0; i < n; i++){
            map[edges[i][0]].Add(edges[i][1]);
            map[edges[i][1]].Add(edges[i][0]);
        }
        used = new bool[n+1];
        dfs(0);
        return res;
        
    }
}

树的直径 #

题目描述 #

思路：回溯法(超时) #

思路：官方 #

树的直径

题目描述

思路：回溯法(超时)

思路：官方