Maximum depth of a binary tree
You get the root of a binary tree: a TreeNode with a value val and two children, left and right, each another TreeNode or None. An empty tree is None.
Return the depth of the tree: start at the root, walk down from parent to child until you reach a leaf (a node with no children), and count the nodes you pass, both ends included. The depth is the largest count over every leaf. An empty tree has depth 0.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [1, 2, 3, None, 4, None, None, 5]Output41 has children 2 and 3, 2 has a right child 4, and 4 has a left child 5. The longest path is 1, 2, 4, 5: four nodes.
root = [7]Output1One node is a path of one node.
root = []Output0An empty tree has no nodes.
0 ≤ number of nodes ≤ 104
-100 ≤ node values ≤ 100
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.