golang 解法, 执行用时: 0 ms, 内存消耗: 3.1 MB, 提交时间: 2023-10-21 19:39:01

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
// 没什么意义，直接每个节点取子节点前2大深度之和的最大值即可
// 深度通过叶子反向累计
func diameter(root *Node) int {
    var ans int
    var helper func(node *Node) int
    helper = func(node *Node) int{
        if node==nil{
            return 0
        }
        var v1,v2 int
        for _,c := range node.Children{
            d := helper(c)
            if d>=v1{
                v1,v2 = d,v1
            }else if d>v2{
                v2 = d
            }
        }
        if v := v1+v2; v>ans{
            ans = v
        }
        return v1+1
    }
    helper(root)
    return ans
}

java 解法, 执行用时: 0 ms, 内存消耗: 41.7 MB, 提交时间: 2023-10-21 19:38:23

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
   protected int diameter = 0;

   /**
    * 返回从给定节点下降的叶子节点的最大深度
    */
   protected int maxDepth(Node node, int currDepth) {
       if (node.children.size() == 0)
           return currDepth;

       // 选择前两个最大深度
       int maxDepth1 = currDepth, maxDepth2 = 0;
       for (Node child : node.children) {
           int depth = maxDepth(child, currDepth + 1);
           if (depth > maxDepth1) {
               maxDepth2 = maxDepth1;
               maxDepth1 = depth;
           } else if (depth > maxDepth2) {
               maxDepth2 = depth;
           }
           // 计算两个最远的叶节点之间的距离。
           int distance = maxDepth1 + maxDepth2 - 2 * currDepth;
           this.diameter = Math.max(this.diameter, distance);
       }

       return maxDepth1;
   }

   public int diameter(Node root) {
       this.diameter = 0;
       maxDepth(root, 0);
       return diameter;
   }
}

java 解法, 执行用时: 0 ms, 内存消耗: 42 MB, 提交时间: 2023-10-21 19:37:57

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
   protected int diameter = 0;

   /**
    * 返回节点的高度
    */
   protected int height(Node node) {
       if (node.children.size() == 0)
           return 0;

       // 选择上面两个最大的高度
       int maxHeight1 = 0, maxHeight2 = 0;
       for (Node child : node.children) {
           int parentHeight = height(child) + 1;
           if (parentHeight > maxHeight1) {
               maxHeight2 = maxHeight1;
               maxHeight1 = parentHeight;
           } else if (parentHeight > maxHeight2) {
               maxHeight2 = parentHeight;
           }
           // 计算两个最远的叶节点之间的距离。
           int distance = maxHeight1 + maxHeight2;
           this.diameter = Math.max(this.diameter, distance);
       }

       return maxHeight1;
   }

   public int diameter(Node root) {
       this.diameter = 0;
       height(root);
       return diameter;
   }
}

java 解法, 执行用时: 0 ms, 内存消耗: 42.1 MB, 提交时间: 2023-10-21 19:37:14

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    int ans;
    public int diameter(Node root) {
        postSearch(root);
        return ans;
    }

    public int postSearch(Node node){
        if(node.children.size() == 0){
            return 0;
        }

        int v1 = 0, v2 = 0;
        for(Node ch : node.children){
            int t = postSearch(ch) + 1;
            if(t >= v1){
                v2 = v1;
                v1 = t;
            }else if(t > v2){
                v2 = t;
            }
        }
        ans = Math.max(ans, v1 + v2);
        return v1;
    }
}

python3 解法, 执行用时: 112 ms, 内存消耗: 18.8 MB, 提交时间: 2023-10-21 19:36:42

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def diameter(self, root: 'Node') -> int:
        """
        :type root: 'Node'
        :rtype: int
        """
        self.adjVex = defaultdict(list)             #邻接表
        self.dfs(root)                              #初始化邻接表，建图

        que = [root]                                #随便选一个点作为起点
        visited = set()
        visited.add(root)                           #记忆化
        cur = root                                  #全局变量，记下第一次BFS的最后一个点
        while que:
            cur_len = len(que)
            for _ in range(cur_len):
                cur = que.pop(0)
                for nxt in self.adjVex[cur]:
                    if nxt not in visited:
                        visited.add(nxt)
                        que.append(nxt)
        visited.clear()
        que = [cur]                                 #第一次BFS最后一个点最为第二次BFS的起点
        visited.add(cur)                            #记忆化
        level = -1                                  #波纹法 记录距离
        while que:
            cur_len = len(que)
            level += 1                          
            for _ in range(cur_len):                #波纹法
                cur = que.pop(0)
                for nxt in self.adjVex[cur]:
                    if nxt not in visited:
                        visited.add(nxt)
                        que.append(nxt)
        return level   


    def dfs(self, rt: 'Node') -> None:              #初始化邻接表，建图
        if not rt:
            return 
        for ch in rt.children:
            self.adjVex[rt].append(ch)
            self.adjVex[ch].append(rt)

            self.dfs(ch)

python3 解法, 执行用时: 60 ms, 内存消耗: 18 MB, 提交时间: 2023-10-21 19:35:54

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def diameter(self, root: 'Node') -> int:
        """
        :type root: 'Node'
        :rtype: int
        """
        self.res = 0
        
        def recur(root):
            if not root:
                return 0
            
            temp1, temp2 = 0, 0
            for child in root.children:
                temp = recur(child)
                temp1, temp2 = max(temp1, temp), min(temp1, max(temp2, temp))
                
            self.res = max(self.res, temp1 + temp2)
            return max(temp1, temp2) + 1
        
        recur(root)
        return self.res

cpp 解法, 执行用时: 16 ms, 内存消耗: 10.8 MB, 提交时间: 2023-10-21 19:35:23

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
// code1 DFS/树形DP 写法一
class Solution {
public:
    int res = 0;
    // 自定义函数
    int dfs(Node *root) {
        if (root == NULL)
            return 0;
        int maxDepth1 = 0, maxDepth2 = 0, height;
        for (auto child : root->children) {
            height = dfs(child);
            if (height >= maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = height;
            }
            else if (height > maxDepth2)
                maxDepth2 = height;
        }
        res = max(res, maxDepth1 + maxDepth2);
        return max(maxDepth1, maxDepth2) + 1;
    }
    
    int diameter(Node *root) {
        dfs(root); // post-order
        return res;
    }
};

// code2 DFS/树形DP 写法二
class Solution2 {
    int res = 0;
public:
    int diameter(Node *root) {
        dfs(root);
        return res - 1;
    }
    // 自定义函数
    int dfs(Node *node) {
        if (node == NULL)
            return 0;
        vector<int> depth;
        for (auto child : node->children)
            depth.push_back(dfs(child));
        sort(depth.rbegin(), depth.rend());

        int n = depth.size();
        if (n >= 2) {
            res = max(res, depth[0] + depth[1] + 1);
            return depth[0] + 1;
        }
        else if (n == 1) {
            res = max(res, depth[0] + 1);
            return depth[0] + 1;
        } else {
            res = max(res, 1);
            return 1;
        }
    }
};

// code3 两次BFS
class Solution3 {
public:
    unordered_map<Node *, vector<Node *>> adjVex; // 存储邻接表
    // 自定义函数
    void dfs(Node *root) { // 初始化邻接表，建立图
        if (!root)
            return;
        for (Node *child : root->children) {
            adjVex[root].push_back(child);
            adjVex[child].push_back(root); // 无向图，双向记录
            dfs(child);
        }
    }
    
    int diameter(Node *root) {
        dfs(root);                     // 先建立图，初始化邻接表
        unordered_set<Node *> visited; // 记忆化
        queue<Node *> q;               // bfs
        q.push(root);                  // 选一个节点作为起点
        visited.insert(root);
        Node *cur; // 全局变量，记录第一次BFS的终点，作为第二次BFS的起点
        while (q.size()) {
            int len = q.size();
            for (int i = 0; i < len; ++i) {
                cur = q.front();
                q.pop();
                for (Node *next : adjVex[cur]) {
                    if (visited.count(next) == 0) {
                        visited.insert(next); // 入队时标记和出队时标记效果同
                        q.push(next);
                    }
                }
            }
        }
        visited.clear();     // 清空记忆化
        q.push(cur);         // 第一次BFS的最远的点，作为第二次BFS的起点
        visited.insert(cur); // 因为它是直径的一个端点
        int level = -1;      // 记录距离
        while (q.size()) {
            level++;
            int len = q.size();
            for (int i = 0; i < len; ++i) { // 波纹法
                cur = q.front();
                q.pop();
                for (Node *next : adjVex[cur]) {
                    if (visited.count(next) == 0) {
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
        }
        return level;
    }
};