104. Maximum Depth of Binary Tree

Description:

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

# 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
'''
[1] bottom-up)

code::
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        left_depth=self.maxDepth(root.left)
        right_depth=self.maxDepth(root.right)
        return max(left_depth,right_depth)+1

-T/C: O(n)
-S/C: O(h)
'''
'''
[2] top-down)

idea::
update depth

code::
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.getDepth(root,0)
        
    
    def getDepth(self,root,depth):
        if not root:
            return depth
        return max(self.getDepth(root.left,depth+1),self.getDepth(root.right,depth+1))
        
-T/C: O(n)
-S/C: O(h)
'''

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.getDepth(root,0)
        
    
    def getDepth(self,root,depth):
        if not root:
            return depth
        return max(self.getDepth(root.left,depth+1),self.getDepth(root.right,depth+1))