Given the root
of a binary tree, return its maximum depth the level of the farthest leaf (i.e. the height +1 of the tree).
A binary tree's 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)
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
Example 2:
Input: root = [1,null,2] Output: 2
Example 3:
Input: root = [] Output: 0
Example 4:
Input: root = [0] Output: 1
Constraints:
[0, 104]
.-100 <= Node.val <= 100
Source
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
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
left = max_height(root.left)
right = max_height(root.right)
return 1 + max(left, right)
def max_depth(root):
"""Same as above. This is what is actually asked for in this question
Though strictly speaking depth = counting edges and not nodes
Note: this solution CAN NOT be applied as such for min depth (see leetcode 111)."""
if not root:
return 0 # strictly speaking height(leaf) = 0 ==> height(None) should be -1 (by convention)
left = max_depth(root.left)
right = max_depth(root.right)
return 1 + max(left, right)
def max_depth(root):
"""Same as above.
Note: this solution CAN be applied as such for min depth (see leetcode 111)."""
if not root:
return 0 # strictly speaking height(None) should be -1
if not root.left and not root.right: # not strictly
return 1 # needed (but speeds up)
if not root.left: # However
return 1 + max_depth(root.right) # it would be needed
if not root.right: # if we were looking for
return 1 + max_depth(root.left) # min height instead
return 1 + max(max_depth(root.left), max_depth(root.right))
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
we keep track of the highest value we saw so far
"""
def dfs(node, depth):
nonlocal max_depth
# base case
if not node:
if depth > max_depth:
max_depth = depth
return
depth += 1
left = dfs(node.left, depth)
right = dfs(node.right, 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:
if node:
depth = level # last level we see will be the depth
queue += (node.left, level+1), (node.right, level+1),
return depth
from collections import deque
def max_depth(root):
"""BFS using a top down iterative approach with a queue."""
if not root:
return 0
queue = deque()
queue.append((root, 1))
depth = 0
while queue:
node, level = queue.popleft()
if node:
depth = level # last level we see will be the depth
queue += (node.left, level+1), (node.right, level+1),
return depth
def max_level(root):
"""BFS using a bottom up iterative approach with a list."""
# Start with a level traversal (using a stack)
queue = [root]
for node in queue:
if node:
queue += node.left, node.right # last nodes --> full layer of "None"
# then, traverse nodes in reverse (i.e from bottom layer)and update their height
# by conv. height of bottom nodes = 0 (i.e last nodes being "None" have depth = -1)
height = {None: -1}
for node in reversed(queue):
if node:
height_left = height[node.left]
height_right = height[node.right]
height[node] = 1 + max(height_left, height_right)
return 1+height[root]
from collections import deque
def max_level(root):
"""BFS using a bottom up iterative approach with a deque"""
queue = deque()
queue.append(root)
traversal = deque()
while queue:
node = queue.popleft()
if node:
traversal.appendleft(node)
queue += node.left, node.right # last nodes --> full layer of "None"
height = {None: -1}
while traversal:
node = traversal.popleft()
if node:
height_left = height[node.left]
height_right = height[node.right]
height[node] = 1 + max(height_left, height_right)
return 1+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()
if node:
depth = max(depth, level) # keep track of max depth
stack += (node.left, level+1), (node.right, level+1),
return depth