Skip to content

893. All Nodes Distance K In Binary Tree

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

Problem - All Nodes Distance K In Binary Tree

Medium

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 distance k from the target node.

You can return the answer in any order.

 

Example 1:

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:

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.
  • 0 <= k <= 1000

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        def dfs(root, parent):
            if root is None:
                return
            dic[root] = parent
            dfs(root.left, root)
            dfs(root.right, root)

        def dfs2(root, parent, k):
            if root is None:
                return 0
            if k == 0:
                result.append(root.val)
                return

            for nxt in (root.left, root.right, dic[root]):
                if nxt != parent:
                    dfs2(nxt, root, k - 1)

        dic = {}
        dfs(root, None)
        result = []
        dfs2(target, None, k)

        return result

Submission Stats:

  • Runtime: 41 ms (92.99%)
  • Memory: 19.8 MB (48.93%)