863. All Nodes Distance K in Binary Tree (Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Implementing Parent Pointers

Node에 parent포인터를 하나 더 만드는 방법이다. dfs로 먼저 모든 노드에 parent를 만들어 준다음, 다음 dfs에 target node부터 시작해서 거리가 k가 되면 그 노드의 val를 ans에 append한다.

# 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 add_parent(child, parent):
            if child:
                child.parent = parent
                add_parent(child.left, child)
                add_parent(child.right, child)

        add_parent(root, None)

        ans = []
        visited = set()
        def dfs(node, d):
            if not node or node in visited:
                return

            visited.add(node)
            if d == k:
                ans.append(node.val)
                return

            dfs(node.parent, d+1)
            dfs(node.left, d+1)
            dfs(node.right, d+1)

        dfs(target, 0)

        return ans

Time Complexity: O(n) add_parent와 dfs는 각각 O(n)이 소요된다.

Space Complexity: O(n) visited에는 최대 n개의 노드들을 저장한다. 또한 recursive한 dfs이므로 O(n)개의 메모리가 필요하다(binary tree가 한쪽에만 몰려있는 최악의 경우에).

2) DFS on Equivalent Graph

이 방법은 모든 node의 val이 unique하다는 점을 사용하여 defaultdict(list)로 만들어진 graph를 통해 답을 구해내는 방법이다.

# 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]:
        graph = defaultdict(list)

        def create_graph(child, parent):
            if child and parent:
                graph[child.val].append(parent.val)
                graph[parent.val].append(child.val)
            if child.left:
                create_graph(child.left, child)
            if child.right:
                create_graph(child.right, child)

        create_graph(root, None)

        ans = []
        visited = {target.val}
        
        def dfs(val, d):
            if d == k:
                ans.append(val)
                return

            for neighbor in graph[val]:
                if neighbor not in visited:
                    visited.add(val)
                    dfs(neighbor, d+1)

        dfs(target.val, 0)
        return ans

Time Complexity: O(n) create_graph와 dfs는 각각 O(n)이 소요된다.

Space Complexity: O(n) graph와 visited에는 최대 n개의 노드들을 저장한다. 또한 recursive한 dfs이므로 O(n)개의 메모리가 필요하다(binary tree가 한쪽에만 몰려있는 최악의 경우에).

3) BFS on Equivalent Graph

DFS와 마찬가지로 먼저 graph를 만들고, 그 다음에 bfs방식으로 답을 구하는 방법이다.

# 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]:
        graph = defaultdict(list)

        def create_graph(child, parent):
            if child and parent:
                graph[child.val].append(parent.val)
                graph[parent.val].append(child.val)
            if child.left:
                create_graph(child.left, child)
            if child.right:
                create_graph(child.right, child)

        create_graph(root, None)

        ans = []
        visited = {target.val}

        queue = deque([(target.val, 0)])
        while queue:
            val, d = queue.popleft()

            if d == k:
                ans.append(val)
                continue
            
            for neighbor in graph[val]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, d+1))

        return ans

Time Complexity: O(n) create_graph와 dfs는 각각 O(n)이 소요된다.

Space Complexity: O(n) graph와 visited에는 최대 n개의 노드들을 저장한다. 또한 recursive한 dfs이므로 O(n)개의 메모리가 필요하다(binary tree가 한쪽에만 몰려있는 최악의 경우에).