# 找 tree 的距離

{%hackmd theme-dark %}

root=Node() k=2

1
2 3
4 5 6 7

k = 1-1000

root(1) = 0

(2) = 1
(3) = 1

def findKdistanceNode(root, target, k):
    
    graph = defaultdict(list)
    
    # traverse tree into graph
    # O(N)
    def buildGraph(node):
        if not node:
            return
        #1 
        if node.left:
            graph[node.val].append(node.left) #1:[2]
            graph[node.left.val].append(node) #2:[1]
            buildGraph(node.left)
        if node.right:
            graph[node.val].append(node.right)#1:[2, 3]
            graph[node.right.val].append(node)#3:[1]
            buildGraph(node.right)
            
    buildGraph(root)
    
    
    if target.val not in graph:
        return []
    
    # 1:[2, 3]
    # 2:[1, 4, 5]
    # 3:[1, 6, 7]
    # 4:[2]
    # ...
    
    # ta = 2, k = 1
    
    # use BFS to find distance k
    ans = []
    queue = [(target.val, 0)]
    seen = set()
    # O(N)
    while queue:
        cur, distance = queue.pop()# cur = 2 , 5, 4
        
        if cur in seen: 
            continue
        seen.add(cur) # (2, 1)
        
        if distance == k: # 0 5
            ans.append(cur) # [5, 4, 1]
            continue
        
        for nei in graph[cur]: # 2:[1, 4, 5]
            queue.append((nei.val, distance+1))
    return ans # [1 4 5]
    
    # N = tree nodes number 
    # TC: O(N)

def findKdistanceNode(root, k):
    ans = []
    def helper(node, level):
        # n1 l=0
        # n2 l=1
        # n4 l=2
        if not node:
            return
        
        if level == k:
            # ans = [4....]
            ans.append(node.val)
            return
        
        helper(node.left, level+1) # n2 l=1, n4 l=2
        helper(node.right, level+1)#
        
    helper(root, 0)
    return ans
        

###### tags: `mock interview` `面試`