List Every Node a Fixed Number of Steps From a Chosen Node
Implement nodesAtDistance
You are given the root of a binary tree with distinct node values, a value target and an integer k. The distance between two nodes is the number of parent-child connections on the path joining them, and that path may go up and then down. Return the values of all nodes that are exactly k steps away from the node holding target, sorted in ascending order. If the target is missing or no node is that far away, return an empty list.
A tree node has no link to its parent, so one approach adds those links by converting the tree to a graph. The other lets the recursion report back the distance to the target and searches the sibling side of each ancestor.
Example 1:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], target = 8, k = 2
Output: [2,6,9,13,22]
Example 2:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], target = 8, k = 1
Output: [4,11,15]
Example 3:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], target = 13, k = 3
Output: [4,15]
+ 15 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 1 ≤ node.val ≤ 1000 - ●
target is a value between 1 and 1000 that may or may not be in the tree; 0 ≤ k ≤ 100 - ●
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ●
The distance between two nodes is the number of parent-child connections on the path between them (the path may go up and then down). Return the values of ALL nodes at distance exactly k from the target node, in ascending order. If the target is not in the tree, or no node is that far away, return an empty list
root =
target =
k =