给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

输出：[7,4,1]

解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

解法：

• 先DFS遍历，建立conn邻接表。
• BSF遍历target节点的邻接节点保存在一个队列中，并将访问过的节点记录下来。

class Solution:
    def distanceK(self, root, target, K):
        """
        :type root: TreeNode
        :type target: TreeNode
        :type K: int
        :rtype: List[int]
        """
        # 建立邻接表
        conn = collections.defaultdict(list)
        def connect(p,c):
            if p and c:
                conn[p.val].append(c.val)
                conn[c.val].append(p.val)
            if c.left:
                connect(c,c.left)
            if c.right:
                connect(c,c.right)
        connect(None,root)
        # print(conn)

        # BFS搜索
        q=[target.val]
        vis=set(q)
        for k in range(K):
            new_q=[]
            for node in q:
                for i in conn[node]:
                    if i not in vis:
                        vis.add(i)
                        new_q.append(i)
            q=new_q
            # print(q)
        return q
# 执行结果：通过
# 执行用时 :56 ms,在所有 Python3 提交中击败了74.64%的用户
# 内存消耗 :13.8 MB , 在所有 Python3 提交中击败了5.13%的用户

赏

谢谢你请我吃糖果

支付宝

微信