863. All Nodes Distance K in Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def distanceK(self, root, target, K):
        """
        :type root: TreeNode
        :type target: TreeNode
        :type K: int
        :rtype: List[int]
        main idea: build a undirected graph using dfs, use bfs starting from target node to do level order traverse until K times
        
        time O(N) space O(N)
        """
        d = collections.defaultdict(list)
        res = []
        seen = set()
        # step1: dfs/ preorder traversal  build graph using dictdict(list)
        def build(par,child):
            if par and child:
                d[par.val].append(child.val)
                d[child.val].append(par.val)
            if child.left:
                build(child,child.left)
            if child.right:
                build(child,child.right)
        build(None,root)
        # step2: bfs 
        q = [target.val]
        seen.add(target.val)
        for i in range(K):
            next_q = []
            for q_val in q:
                for nei in d[q_val]:
                    if nei not in seen:
                        next_q.append(nei)
                        # ! to avoid reapeated elements added into the queue  
                        seen.add(nei)
            q = next_q
        return q