Minimum depth
You get the root of a binary tree. A leaf is a node with no children: its left and right are both None.
Return the tree's minimum depth: the number of nodes on the shortest path that starts at the root and goes down from parent to child until it stops at a leaf, both ends included. An empty tree (root is None) has minimum depth 0.
A node with one child is not a leaf, so no path can stop there.
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, 4, 5, None, 6, 7, 8, None, 9]Output33 has a right child, 6, so 3 is not a leaf. The shallowest leaf is 6, on level 3, the last node of its level. The other leaves, 7, 8 and 9, are one level lower.
root = [5, None, 4, None, 3, None, 2]Output4Every node above 2 has only a right child, so the only leaf is 2, at the bottom, and the only path to it has 4 nodes.
root = []Output0No nodes, so no path.
0 ≤ number of nodes ≤ 105
-1,000 ≤ node value ≤ 1,000
The tree can be one chain of 105 nodes, far deeper than the 5,000 nested calls this lab allows (about 1,000 in plain Python).
The function may be called many times on the same tree.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.