Leetcode 104. Maximum Depth of Binary Tree (Python)

Related Topic

Depth-First-Search. Tree.

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Sample I/O

Given binary tree [3,9,20,null,null,15,7],

Example 1

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

Note:

A leaf is a node with no children.

Methodology

This question can be solved by Depth First Search and it is very esential and classic DFS question for Tree.

To find the maximum depth, we need to find the maxmium depth from left subtree depth and right substree depth and plus 1 as the root is count as 1 depth.

Code

def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

BigO

We go through each node once therefore the time complexity is O(n)