Description#
Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.
The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.
(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.
Example 2:
Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4
Example 3:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 7
Constraints:
- The depth of the n-ary tree is less than or equal to
1000. - The total number of nodes is between
[1, 104].
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| """
# 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
"""
def dfs(root):
if root is None:
return 0
nonlocal ans
m1 = m2 = 0
for child in root.children:
t = dfs(child)
if t > m1:
m2, m1 = m1, t
elif t > m2:
m2 = t
ans = max(ans, m1 + m2)
return 1 + m1
ans = 0
dfs(root)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| /*
// 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 {
private int ans;
public int diameter(Node root) {
ans = 0;
dfs(root);
return ans;
}
private int dfs(Node root) {
if (root == null) {
return 0;
}
int m1 = 0, m2 = 0;
for (Node child : root.children) {
int t = dfs(child);
if (t > m1) {
m2 = m1;
m1 = t;
} else if (t > m2) {
m2 = t;
}
}
ans = Math.max(ans, m1 + m2);
return 1 + m1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| /*
// 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;
}
};
*/
class Solution {
public:
int ans;
int diameter(Node* root) {
ans = 0;
dfs(root);
return ans;
}
int dfs(Node* root) {
if (!root) return 0;
int m1 = 0, m2 = 0;
for (Node* child : root->children) {
int t = dfs(child);
if (t > m1) {
m2 = m1;
m1 = t;
} else if (t > m2)
m2 = t;
}
ans = max(ans, m1 + m2);
return 1 + m1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func diameter(root *Node) int {
ans := 0
var dfs func(root *Node) int
dfs = func(root *Node) int {
if root == nil {
return 0
}
m1, m2 := 0, 0
for _, child := range root.Children {
t := dfs(child)
if t > m1 {
m2, m1 = m1, t
} else if t > m2 {
m2 = t
}
}
ans = max(ans, m1+m2)
return 1 + m1
}
dfs(root)
return ans
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| """
# 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
"""
def build(root):
nonlocal d
if root is None:
return
for child in root.children:
d[root].add(child)
d[child].add(root)
build(child)
def dfs(u, t):
nonlocal ans, vis, d, next
if u in vis:
return
vis.add(u)
for v in d[u]:
dfs(v, t + 1)
if ans < t:
ans = t
next = u
d = defaultdict(set)
vis = set()
build(root)
ans = 0
next = None
dfs(root, 0)
vis.clear()
dfs(next, 0)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| /*
// 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 {
private Map<Node, Set<Node>> g;
private Set<Node> vis;
private Node next;
private int ans;
public int diameter(Node root) {
g = new HashMap<>();
build(root);
vis = new HashSet<>();
next = root;
ans = 0;
dfs(next, 0);
vis.clear();
dfs(next, 0);
return ans;
}
private void dfs(Node u, int t) {
if (vis.contains(u)) {
return;
}
vis.add(u);
if (t > ans) {
ans = t;
next = u;
}
if (g.containsKey(u)) {
for (Node v : g.get(u)) {
dfs(v, t + 1);
}
}
}
private void build(Node root) {
if (root == null) {
return;
}
for (Node child : root.children) {
g.computeIfAbsent(root, k -> new HashSet<>()).add(child);
g.computeIfAbsent(child, k -> new HashSet<>()).add(root);
build(child);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| /*
// 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;
}
};
*/
class Solution {
public:
unordered_map<Node*, unordered_set<Node*>> g;
unordered_set<Node*> vis;
Node* next;
int ans;
int diameter(Node* root) {
build(root);
next = root;
ans = 0;
dfs(next, 0);
vis.clear();
dfs(next, 0);
return ans;
}
void dfs(Node* u, int t) {
if (vis.count(u)) return;
vis.insert(u);
if (ans < t) {
ans = t;
next = u;
}
if (g.count(u))
for (Node* v : g[u])
dfs(v, t + 1);
}
void build(Node* root) {
if (!root) return;
for (Node* child : root->children) {
g[root].insert(child);
g[child].insert(root);
build(child);
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| /**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func diameter(root *Node) int {
g := make(map[*Node][]*Node)
vis := make(map[*Node]bool)
next := root
ans := 0
var build func(root *Node)
build = func(root *Node) {
if root == nil {
return
}
for _, child := range root.Children {
g[root] = append(g[root], child)
g[child] = append(g[child], root)
build(child)
}
}
build(root)
var dfs func(u *Node, t int)
dfs = func(u *Node, t int) {
if vis[u] {
return
}
vis[u] = true
if t > ans {
ans = t
next = u
}
if vs, ok := g[u]; ok {
for _, v := range vs {
dfs(v, t+1)
}
}
}
dfs(next, 0)
vis = make(map[*Node]bool)
dfs(next, 0)
return ans
}
|
