1.1. 题目
1.1.1. 二叉树中所有距离为 K 的结点
给定一个二叉树（具有根结点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
注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
注意:
- 给定的树是非空的。
- 树上的每个结点都具有唯一的值
0 <= node.val <= 500。 - 目标结点
target是树上的结点。 - 0 <= K <= 1000.
1.1.2. 题解:
- 一普通二叉树,然后找到到某个指定节点距离为k的节点的值
- 每个节点的值是唯一的
- 可以理解成到这个节点的路径距离为k的节点
1.1.3. 思路:
- 肯定是递归来解比较方便
- 假设只往下找,那么从 target节点往下 左右节点往下找,找到k层的,就差不多是符合条件的
- 但是现在可以往上找,往上找之后,还按照正常来遍历,但是重复的得去掉,那么遍历逻辑是一样的了
- 如果一个节点已经遍历过了,那么他的左右子节点,父节点都不需要再去一趟了.. 所以定义一个存储遍历记录
1.1.4. 代码:
点击显示
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
// 如果节点为空, 直接返回
if root == nil || target == nil {
return nil
}
// 定义个一个map,存储该节点的父节点, key为该节点, value为父节点
// 因为val是唯一的,你也可以存储val map[int]int 也可以
m := make(map[*TreeNode]*TreeNode)
// 定义一个匿名函数,找出所有节点对应的父节点
var all func(node *TreeNode)
all = func(temp *TreeNode) {
// 如果为空,说明都按最底下了,直接返回
if temp == nil {
return
}
// 如果左节点存在,那么存储一下这个左节点和它的父节点
if temp.Left != nil {
m[temp.Left] = temp
}
// 如果右节点存储,那么存储一下这个右节点和它的父节点
if temp.Right != nil {
m[temp.Right] = temp
}
// 递归遍历左节点
all(temp.Left)
// 递归遍历右节点
all(temp.Right)
}
// 遍历整个树
all(root)
// 定义返回值
var res []int
// 重复的节点,只需要定义一个map,用key来判断是否存储,value不重要,所以空结构体来表示
cf := make(map[*TreeNode]struct{})
// 定义一个匿名函数,遍历节点和深度
var find func(node *TreeNode, deep int)
find = func(node *TreeNode, deep int) {
// 如果到最底下了,就返回
if node == nil {
return
}
// 如果这个节点已经遍历过了,直接返回
if _, ok := cf[node]; ok {
return
}
// 如果深度符合,那么这个节点是符合条件的
if deep == k {
res = append(res, node.Val)
return
}
// 记录该节点已经被遍历过
cf[node] = struct{}{}
// 遍历左节点,深度+1
find(node.Left, deep+1)
// 遍历右节点,深度+1
find(node.Right, deep+1)
// 遍历父节点,深度+1
find(m[node], deep+1)
}
// 从目标节点开始遍历
find(target, 0)
return res
}