742. Closest Leaf in a Binary Tree

"""
742. Closest Leaf in a Binary Tree

树本身就是一个无向图，所以先建立一个无向图。这道题问的是叶节点，所以这道题的技巧是用一个set来维护所有的叶节点。之后再用BFS的时候就可以查找是否是叶节点。 之前自己就是卡在了不知道怎么寻找叶节点上面。
"""
from collections import deque, defaultdict


class Solution(object):
    def connect(self, root, graph, leaves):
        if not root:
            return

        if not root.left and not root.right:    # 叶节点
            leaves.add(root.val)
            return

        if root.left:
            graph[root] = root.left
            graph[root.left] = root
            self.connect(root.left, graph, leaves)

        if root.right:
            graph[root] = root.right
            graph[root.right] = root
            self.connect(root.right, graph, leaves)

    def findClosestLeaf(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        graph = defaultdict(list)
        leaves = set()                    # 运用set便于检索
        self.connect(root, graph, leaves) # 建立无向图 and 把叶节点装进Set便于之后查找。

        visited = set()                   # visited

        q = deque()                       # BFS
        q.append(k)
        while q:
            num = len(q)
            for i in range(num):
                node = q.popleft()
                if node in leaves:
                    return node
                if not node in visited:
                    visited.add(node)
                    q.extend(graph[node])

        return