Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distancekfrom the target node.
You can return the answer in any order.
Example 1:
1 2 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Example 2:
1 2
Input: root = [1], target = 1, k = 3 Output: []
Constraints:
The number of nodes in the tree is in the range [1, 500].
0 <= Node.val <= 500
All the values Node.val are unique.
target is the value of one of the nodes in the tree.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
classSolution: defdistanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]: nodeParentDict = dict() defdfsFindParent(node): if node: if node.left: nodeParentDict[node.left] = node if node.right: nodeParentDict[node.right] = node dfsFindParent(node.left) dfsFindParent(node.right) dfsFindParent(root) if k == 0: return [target.val] result = [] queue = collections.deque() visited = set() queue.append(target) visited.add(target) level = 0 while queue and level < k: level += 1 for _ in range(len(queue)): now = queue.popleft() for nextNode in [nodeParentDict[now] if now in nodeParentDict elseNone, now.left, now.right]: if nextNode and nextNode notin visited: if level == k: result.append(nextNode.val) queue.append(nextNode) visited.add(nextNode) return result