Given a n-ary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: 3
Example 2:
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: 5
Constraints:
[0, 104].1000.program main
implicit none
type :: Node
integer :: val
type(Node), pointer :: left(:) => null()
type(Node), pointer :: right(:) => null()
end type
type(Node), target :: root
type(Node), pointer :: curr
integer :: i, j
! Example 1
allocate(root%left(1))
allocate(root%right(2))
root%val = 1
root%left(1)%val = 3
root%right(1)%val = 2
root%right(2)%val = 4
print '(I0)', maxDepth(root)
! Example 2
deallocate(root%left)
deallocate(root%right)
allocate(root%left(2))
allocate(root%right(3))
root%val = 1
root%left(1)%val = 5
root%left(2)%val = 6
root%right(1)%val = 7
root%right(2)%val = 8
root%right(3)%val = 9
root%right(3)%left(1)%val = 10
root%right(3)%right(1)%val = 11
root%right(3)%right(2)%val = 12
root%right(3)%right(2)%left(1)%val = 13
root%right(3)%right(2)%right(1)%val = 14
print '(I0)', maxDepth(root)
contains
function maxDepth(root) result(depth)
implicit none
class(Node), intent(in) :: root
integer :: depth
type(Node), pointer :: curr
integer :: i
depth = 0
curr => root
do while (associated(curr))
if (associated(curr%left)) then
depth = max(depth, maxDepth(curr%left))
end if
if (associated(curr%right)) then
depth = max(depth, maxDepth(curr%right))
end if
curr => curr%left
end do
end function
end programtemp.f95:53:16:
53 | curr => root
| 1
Error: Pointer assignment target is neither TARGET nor POINTER at (1)
temp.f95:56:44:
56 | depth = max(depth, maxDepth(curr%left))
| 1
Error: Rank mismatch in argument ‘root’ at (1) (scalar and rank-1)
temp.f95:56:35:
56 | depth = max(depth, maxDepth(curr%left))
| 1
Error: Function ‘maxdepth’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:59:44:
59 | depth = max(depth, maxDepth(curr%right))
| 1
Error: Rank mismatch in argument ‘root’ at (1) (scalar and rank-1)
temp.f95:59:35:
59 | depth = max(depth, maxDepth(curr%right))
| 1
Error: Function ‘maxdepth’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:61:12:
61 | curr => curr%left
| 1
Error: Different ranks in pointer assignment at (1)
! This is a Fortran implementation of the problem.
! The program takes a n-ary tree as input and outputs its maximum depth.
program max_depth
implicit none
! Declare variables
integer :: n, i, j, k, l, m, n_nodes, max_depth
integer, allocatable :: nodes(:)
! Read the number of nodes in the tree
read (*,*) n_nodes
! Allocate memory for the nodes
allocate (nodes(n_nodes))
! Read the nodes of the tree
do i = 1, n_nodes
read (*,*) nodes(i)
end do
! Initialize the maximum depth
max_depth = 0
! Iterate over the nodes
do i = 1, n_nodes
! If the node is not null, increment the maximum depth
if (nodes(i) /= 0) then
max_depth = max_depth + 1
end if
end do
! Output the maximum depth
write (*,*) max_depth
end program max_depth
temp.f95:9:47:
9 | integer :: n, i, j, k, l, m, n_nodes, max_depth
| 1
Error: Symbol ‘max_depth’ at (1) cannot have a type
temp.f95:24:10:
24 | max_depth = 0
| 1
Error: ‘max_depth’ at (1) is not a variable
temp.f95:30:18:
30 | max_depth = max_depth + 1
| 1
Error: ‘max_depth’ at (1) is not a variable
temp.f95:35:21:
35 | write (*,*) max_depth
| 1
Error: Symbol at (1) is not appropriate for an expression
temp.f95:19:4:
19 | do i = 1, n_nodes
| 1
Error: Symbol ‘i’ at (1) has no IMPLICIT type
temp.f95:13:18:
13 | read (*,*) n_nodes
| 1
Error: Symbol ‘n_nodes’ at (1) has no IMPLICIT type; did you mean ‘nodes’?
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
def max_depth(root):
if root is None:
return 0
max_depth = 0
for child in root.children:
max_depth = max(max_depth, max_depth(child))
return max_depth + 1
The algorithm used for all the language implementations is Depth First Traversal. The base case checks if the current root is null or not. If it is null, the function returns 0. Then, we iterate through each child node in the children list and calculate the maximum depth from each child node by making a recursive call. The maximum depth from a child node is added to the current depth which is initialized to 0. Finally, we return the maximum depth + 1 to account for the current 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;
}
};
int maxDepth(Node* root) {
if (!root) return 0;
int max_depth = 0;
for (Node* child : root->children) {
max_depth = max(max_depth, maxDepth(child));
}
return max_depth + 1;
}
The algorithm used for all the language implementations is Depth First Traversal. The base case checks if the current root is null or not. If it is null, the function returns 0. Then, we iterate through each child node in the children list and calculate the maximum depth from each child node by making a recursive call. The maximum depth from a child node is added to the current depth which is initialized to 0. Finally, we return the maximum depth + 1 to account for the current node.