863.All_Nodes_Distance_K_in_Binary_Tree(Medium).md

863. All Nodes Distance K in Binary Tree (Medium)

Date and Time: Dec 9, 2024, 1:00 (EST)

Link: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree

Question:

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

Walk-through:

1. Build an undirected graph to connect two connected nodes together.

2. Run BFS from [target, 0] from distance = 0, we append all current node's neighbors into deque[]. When a node has distance == k, we append this node.val into res[].

Python Solution:

# 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]:
        # Build undirected graph to connect each two nodes
        # Run BFS from target with depth 0 to add all the nodes from current neighbors into deque
        # When distance == k, add this node into res[]

        # TC: O(n), n is total nodes, SC: O(n)
        graph = collections.defaultdict(list)
        def buildMap(curr, prev):
            if curr and prev:
                graph[curr].append(prev)
                graph[prev].append(curr)
            if curr.left:
                buildMap(curr.left, curr)
            if curr.right:
                buildMap(curr.right, curr)
        buildMap(root, None)

        deque = collections.deque([(target, 0)])
        visited = set([target])
        res = []
        while deque:
            node, distance = deque.popleft()
            if distance == k:
                res.append(node.val)
                continue
            for neighbor in graph[node]:
                if neighbor not in visited:
                    deque.append((neighbor, distance + 1))
                    visited.add(neighbor)
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$