Interview challenge · easy · binary-tree, recursion, dfs, bfs
Maximum Depth of Binary Tree
El reto
El enunciado va en inglés, igual que en el vídeo.
Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf.
Example
3
/ \
9 20
/ \
15 7 -> 3Idea: the depth of a tree is one plus the deeper of its two subtrees, and an empty tree has depth zero. Time O(n), space O(h).
La solución
# Max Depth of Binary Tree - ayotl.dev
class T:
def __init__(self, v, l=None, r=None):
self.v, self.l, self.r = v, l, r
def max_depth(t):
if not t:
return 0 # empty tree
# this node + the deeper subtree
return 1 + max(max_depth(t.l),
max_depth(t.r))
root = T(3, T(9), T(20, T(15), T(7)))
print(max_depth(root))
print(max_depth(T(1, None, T(2))))
$ python3 maximum_depth_of_binary_tree.py
3
2