480. Exactly K Away
A village's footpaths form a tree: every junction links to at most two junctions below it and to one junction above it (except the topmost junction). The junctions are stored in root as a binary tree whose node values, the junction ids, are all distinct. A courier starts at the junction whose id equals target and may walk along a footpath in either direction, up to a parent or down to a child, one step per footpath.
Return the ids of all junctions whose shortest route from the target junction has exactly k steps, sorted in ascending order. If no junction is exactly k steps away, return an empty array. The target id is guaranteed to occur in the tree, and for k = 0 the answer is just the target itself.
Example 1
- Input:
- root = [8,3,10,1,6,null,14,null,null,4,7,13]target = 3k = 2
- Output:
- [4,7,10]
- Explanation:
From node 3, the nodes two steps away are 4 and 7 (below 6) and 10 (via the root 8).
Example 2
- Input:
- root = [8,3,10,1,6,null,14,null,null,4,7,13]target = 14k = 3
- Output:
- [3]
- Explanation:
Node 3 is the only node three steps from 14, via 10 and 8.
Example 3
- Input:
- root = [5,2,9], target = 2, k = 3
- Output:
- []
- Explanation:
No node is three steps away from 2 in a tree of three nodes, so the result is empty.
Constraints
1 ≤ number of nodes ≤ 104
-105 ≤ Node.val ≤ 105, all values are distinct
target is the value of some node in the tree
0 ≤ k ≤ 104
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 log n)
- Space
- O(n)