7月28日每日一题：二叉树中所有距离为 K 的结点
题目名称：二叉树中所有距离为 K 的结点
难度：中等
题目描述：
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。答案可以以任何顺序返回。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2输出：[7,4,1]解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1
注意，输入的 "root" 和 "target" 实际上是树上的结点。上面的输入仅仅是对这些对象进行了序列化描述。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
如果target节点是根节点的话，我们直接从根节点遍历并记录距离就可以了，而target不是根节点，我们需要同时congtarget节点去遍历父节点，所以我们先进行一次遍历，记录所有节点的父节点，然后从target结点开始，分别记录左节点、右节点、父节点的距离。
为了避免重复访问节点，我们增加变量prev来记录上一个节点。
编码：
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:d = {}def findParents(node):if node.left:d[node.left] = nodefindParents(node.left)if node.right:d[node.right] = nodefindParents(node.right)findParents(root)res = []prev = Nonedef dfs(node, prev, dist):if dist == k:res.append(node.val)returnif node.left and node.left != prev:dfs(node.left, node,dist+1)if node.right and node.right != prev:dfs(node.right, node,dist+1)if d.get(node) and d[node] != prev:dfs(d[node], node, dist+1)dfs(target, None, 0)return res
运行结果：