LC-0863 Medium LeetCode

863. All Nodes Distance K in Binary Tree

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

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 66% Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


class Solution(object):
    def distanceK(self, root, target, K):
        """
        :type root: TreeNode
        :type target: TreeNode
        :type K: int
        :rtype: List[int]
        """
        def dfs(parent, child, neighbors):
            if not child:
                return
            if parent:
                neighbors[parent.val].append(child.val)
                neighbors[child.val].append(parent.val)
            dfs(child, child.left, neighbors)
            dfs(child, child.right, neighbors)

        neighbors = collections.defaultdict(list)
        dfs(None, root, neighbors)
        bfs = [target.val]
        lookup = set(bfs)
        for _ in xrange(K):
            bfs = [nei for node in bfs
                   for nei in neighbors[node]
                   if nei not in lookup]
            lookup |= set(bfs)
        return bfs

Solution from kamyu104/LeetCode-Solutions · MIT