104. Maximum Depth of Binary Tree

Problem¶

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.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Solve¶

Tree traversal - NLR¶

O(n)

• Go to each node and keep track their deep level
  

  #TODO
  

• Or use simple recursion
  

  # 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 root is None:
              return 0
  
          deep = 1
          if root.left:
              left_deep = self.maxDepth(root.left)
              if deep < left_deep + 1:
                  deep = left_deep + 1
  
          if root.right:
              right_deep = self.maxDepth(root.right)
              if deep < right_deep + 1:
                  deep = right_deep + 1
  
          return deep