459. Nearest Leaf Depth
A delivery drone flies down a tree-shaped network of corridors given by root. It starts at the root and wants to reach any dead end (a node with no children) with as few corridor-nodes visited as possible.
Return the number of nodes on the shortest path from root down to the nearest leaf, counting both the root and the leaf. A tree with one node returns 1. If the tree is empty, return 0. Note that a node with exactly one child is not a leaf, so that path must continue downward.
Example 1
- Input:
- root = [6,3,8,null,4,null,null,null,2]
- Output:
- 2
- Explanation:
Node 8 is a leaf at depth 2 (6, 8), which is nearer than the leaf 2 further down the left side.
Example 2
- Input:
- root = [1,null,4,null,9]
- Output:
- 3
- Explanation:
The root has only a right child, so the single path 1, 4, 9 must be followed to the leaf: 3 nodes.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(w)