LeetCode: Tree Diameter

Posted on August 5, 2019July 26, 2020 by braindenny

Tree Diameter

Similar Problems:

Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.

The tree is given as an array of edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v. Each node has labels in the set {0, 1, …, edges.length}.

Example 1:

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: 
A longest path of the tree is the path 1 - 0 - 2.

Example 2:

Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: 
A longest path of the tree is the path 3 - 2 - 1 - 4 - 5.

Constraints:

0 <= edges.length < 10^4
edges[i][0] != edges[i][1]
0 <= edges[i][j] <= edges.length
The given edges form an undirected tree.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: dfs with array

// https://code.dennyzhang.com/tree-diameter
// Basic Ideas: dfs
//  It's a tree. So it's fully connected and there is no circle
//
// Complexity: Time O(n), Space O(n)
func dfs(start int, dis int, res *int, end *int, states [][]int, visited map[int]bool) {
    if visited[start] {
        return
    }
    visited[start] = true
    if dis+1>*res {
        *res = dis
        *end = start
    }
    for _, node := range states[start] {
        dfs(node, dis+1, res, end, states, visited)
    }
}

func treeDiameter(edges [][]int) int {
    states := make([][]int, len(edges)+1)
    for _, edge := range edges {
        n1, n2 := edge[0], edge[1]
        states[n1] = append(states[n1], n2)
        states[n2] = append(states[n2], n1)
    }
    res := 0
    e := 0
    dfs(0, 0, &res, &e, states, map[int]bool{})  
    dfs(e, 0, &res, &e, states, map[int]bool{})
    return res
}

Solution: dfs with hashmap

// https://code.dennyzhang.com/tree-diameter
// Basic Ideas: dfs
//  It's a tree. So it's fully connected and there is no circle
//
// Complexity: Time O(n), Space O(n)
func dfs(start int, dis int, res *int, end *int, m map[int]map[int]bool, visited map[int]bool) {
    if visited[start] {
        return
    }
    visited[start] = true

    if dis+1>*res {
        *res = dis
        *end = start
    }

    for node, _ := range m[start] {
        dfs(node, dis+1, res, end, m, visited)
    }
}

func treeDiameter(edges [][]int) int {
    m := map[int]map[int]bool{}
    for _, edge := range edges {
        n1, n2 := edge[0], edge[1]
        if _, ok := m[n1]; !ok {
            m[n1] = map[int]bool{}
        }
        if _, ok := m[n2]; !ok {
            m[n2] = map[int]bool{}
        }
        m[n1][n2] = true
        m[n2][n1] = true
    }
    res := 0
    e := 0
    dfs(0, 0, &res, &e, m, map[int]bool{})  
    dfs(e, 0, &res, &e, m, map[int]bool{})
    return res
}

Post Views: 0