LC 0742 [M] Closest Leaf in a Binary Tree - ALawliet/algorithms GitHub Wiki

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findClosestLeaf(self, root, k):
        # Time: O(n)
        # Space: O(n)
        
        G = defaultdict(list)
        leaves = set()
        
        # Graph construction - DFS
        def dfs(node):
            if not node:
                return
            
            if not node.left and not node.right:
                leaves.add(node.val)
                return
            
            u = node.val
            
            if node.left:
                v = node.left.val
                G[u].append(v)
                G[v].append(u)
                dfs(node.left)
                
            if node.right:
                v = node.right.val
                G[u].append(v)
                G[v].append(u)
                dfs(node.right)
                
        dfs(root)
        
        # Graph traversal - BFS

        # queue = [k]
        # while len(queue):
        #     next_queue = []
        #     for node in queue:
        #         if node in leaves:
        #             return node
        #         next_queue += G.pop(node, [])
        #     queue = next_queue
        
        Q = deque([k])
        visited = set()
        while Q:
            for _ in range(len(Q)):
                node = Q.popleft()

                # first leaf found in shortest path
                if node in leaves:
                    return node

                if node not in visited:
                    # Q.extend(G[node])
                    Q += G[node] # add both the left and right children
                    visited.add(node)