""" 0104.1 - Maximum Depth of Binary Tree - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def maxDepth(self, root: Optional[TreeNode]) -> int:
"""Maximum Depth of Binary Tree Function"""
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Tree: [3, 9, 20, null, null, 15, 7] -> depth 3
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().maxDepth(root1)) # 3
# Tree: [1, null, 2] -> depth 2
root2 = TreeNode(1, None, TreeNode(2))
print(Solution().maxDepth(root2)) # 2
# Tree: [] -> depth 0
print(Solution().maxDepth(None)) # 0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0104.2 - Maximum Depth of Binary Tree - Solution 2 - Iterative BFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def maxDepth(self, root: Optional[TreeNode]) -> int:
"""Maximum Depth of Binary Tree Function"""
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Tree: [3, 9, 20, null, null, 15, 7] -> depth 3
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().maxDepth(root1)) # 3
# Tree: [1, null, 2] -> depth 2
root2 = TreeNode(1, None, TreeNode(2))
print(Solution().maxDepth(root2)) # 2
# Tree: [] -> depth 0
print(Solution().maxDepth(None)) # 0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
