Solution to LeetCode 104 Maximum Depth of Binary Tree, LeetCode 111 Minimum Depth of Binary Tree, and LeetCode 559 Maximum Depth of N-ary Tree.
LeetCode 104
Maximum Depth of Binary Tree (Easy) [link]
1] BFS. Use level-order traversal to count the number of levels. Time complexity O(n). Space complexity O(n).
# 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
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
max_depth = 0
if not root:
return max_depth
que = deque([root])
while que:
max_depth += 1
size = len(que)
for i in range(size):
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return max_depth
2] DFS. Time complexity O(n). Space complexity O(height).
# 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
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
LeetCode 111
Minimum Depth of Binary Tree (Easy) [link]
1] BFS. Level-order traversal to count the number of levels. If there is no child, break the while loop and return the count. Time complexity O(n).
# 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
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
que = deque([root])
min_depth = 0
if not root:
return min_depth
while que:
size = len(que)
min_depth += 1
for i in range(size):
cur = que.popleft()
if not cur.left and not cur.right:
return min_depth
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return min_depth
2] DFS. Note that it is possible that one node has only one child. For any node that is not a leaf, we record the min depth. Time complexity O(n). Space complexity O(height)
# 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
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = float('inf')
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth+1
LeetCode 559
Maximum Depth of N-ary Tree (Easy) [link]
1] BFS. Level-order traversal using queue. Time complexity O(n). Space complexity O(n).
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
max_depth = 0
if not root:
return max_depth
que = deque([root])
while que:
size = len(que)
for i in range(size):
cur = que.popleft()
for i in cur.children:
que.append(i)
max_depth += 1
return max_depth
2] DFS. Recursion. Time complexity O(n). Space complexity O(height).
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
max_depth = 0
if not root:
return max_depth
for i in range(len(root.children)):
max_depth = max(max_depth, self.maxDepth(root.children[i]))
return max_depth + 1
