Given a n-ary tree, return its maximum depth the level of the farthest leaf (i.e. the height +1 of the tree).
The maximum depth level is the number of nodes along the longest path from the root node down to the farthest leaf node (see here for a reminder on the difference between depth, level and height)
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:
1000
.[0, 104]
.Source
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children # children = list
def max_height(root):
"""DFS using bottom up recursion
we dig until we reach a leaf (height = 0) and we add +1 for
each node until back to the root.
We return max(height(root)) = height(tree)
Note: the question asks for 1+height
"""
if not root:
return -1 # proper use of height
if not root.children: # needed to avoid max(node for node in []) --> throws an error
return 0 # proper use of height(leaf) = 0)
return max(max_height(node) for node in root.children) + 1
def max_depth(root):
"""Same as above. This is actually what is asked for in the question
Though strictly speaking depth = counting edges and not nodes
"""
if not root:
return 0 # strictly speaking height(leaf) = 0 ==> height(None) should be -1 (by convention)
if not root.children: # base case is needed to avoid max(None) --> throws an error
return 1
# recursive relation
return max(max_depth(node) for node in root.children) + 1
def max_depth(root):
"""alternative version of above solution"""
def dfs(node):
# base cases
if not node:
return 0
if not node.children:
return 1
max_depth = 0
for child in node.children:
child_depth = 1 + dfs(child)
max_depth = max(max_depth, child_depth)
return max_depth
return dfs(root)
def max_depth(root):
"""DFS using Top down recursion
we dig into the tree, adding +1 at each children
until we reach a leaf, where we return the depth we calculated so far
"""
def dfs(node, depth):
# base case
if not node:
return 0
depth += 1
max_depth = depth
for child in node.children:
max_depth = max(max_depth, dfs(child, depth))
return max_depth
depth = dfs(root, 0)
return depth
def max_depth(root):
"""alternative version of above solution"""
def dfs(node, depth):
nonlocal max_depth
# base case
if not node:
return
depth += 1
if not node.children:
if depth > max_depth:
max_depth = depth
return
for child in node.children:
dfs(child, depth)
return
max_depth = 0
dfs(root, 0)
return max_depth
Solve it both recursively and iteratively.
def max_depth(root):
"""BFS using a top down iterative approach with a list."""
if not root:
return 0
queue = [(root, 1)]
depth = 0
for (node, level) in queue:
depth = level # last level we see will be the depth
queue += [(child, level+1) for child in node.children]
return depth
from collections import deque
def max_depth(root):
"""BFS using a top down iterative approach with a deque."""
if not root:
return 0
queue = deque()
queue.append((root, 1))
depth = 0
while queue:
node, level = queue.popleft()
if not node:
continue
depth = level # last level we see will be the depth
queue += [(child, level+1) for child in node.children]
return depth
def max_level(root):
"""BFS using a bottom up iterative approach with a list."""
if not root:
return 0
queue = [root]
for node in queue:
if node:
queue += [child for child in node.children] # last nodes --> full layer of "None"
height = {} # no need for None:0 (as opposed to BST - see leetcode #104) None is never added to stack
for node in reversed(queue):
if not node:
continue
if node.children == []:
height[node] = 1
else:
height[node] = 1 + max(height[n] for n in node.children)
return height[root]
def max_level(root):
"""BFS using a bottom up iterative approach with a deque."""
if not root:
return 0
queue = deque()
queue.append(root)
traversal = deque()
while queue:
node = queue.popleft()
if node:
traversal.appendleft(node)
queue += [child for child in node.children] # last nodes --> full layer of "None"
height = {} # no need for None:0 (as opposed to BST - see leetcode #104) None is never added to stack
while traversal:
node = traversal.popleft()
if not node:
continue
if node.children == []:
height[node] = 1
else:
height[node] = 1 + max(height[n] for n in node.children)
return height[root]
def max_depth(root):
"""DFS using an iterative approach with a stack."""
if not root:
return 0
stack = [(root, 1)]
depth = 0
while stack:
(node, level) = stack.pop()
depth = max(depth, level) # keep track of max depth
stack += [(child, level+1) for child in node.children]
return depth