Leetcode 0742 Closest Leaf in a Binary Tree

Problem statement

https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def findClosestLeaf(self, root, k):
        G = defaultdict(list)
        
        def dfs(node):
            if not node: return
            for child in filter(None, [node.right, node.left]):
                G[child.val].append(node.val)
                G[node.val].append(child.val)
                dfs(child)
        
        dfs(root) 
        visited, queue = set(), deque([k])

        while queue:
            last = queue.popleft()
            visited.add(last)
            if len(G[last]) <= 1 and last != root.val:
                return last
            for neib in G[last][::-1]:
                if neib not in visited:
                    queue.append(neib)
        
        return root.val