# LeetCode 863. All Nodes Distance K in Binary Tree

用户头像
liu_liu
关注
发布于: 2020 年 06 月 01 日
# LeetCode 863. All Nodes Distance K in Binary Tree

@(LeetCode)

问题描述



给定一颗二叉树的根节点 root,目标节点 target,和一个整数 K

返回与目标节点距离为 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。



注意:

  1. 二叉树非空。

  2. 每个节点值都是唯一的,范围在 [0, 500]

  3. target 节点在树中。

  4. 0 <= K <= 1000



想看英文原文的戳这里



解题思路

解法 1



解法 1 也是我自己的解法。



初看这题,我冒出的想法是:计算目标节点所在的层,然后再往下数 K 层,则该层上的所有节点与其距离肯定为 K



但是,又回头看了看栗子,发现没那么简单。其不仅仅包括目标节点的子节点 7、4,而且还包括其兄弟节点 1,也可认为是其父节点的子节点。



栗子分析



先看一个复杂些的栗子,树结构如下图所示。其中 K = 3,红色代表目标节点 5





我们从图中可以看出,与其距离为 3 的节点包括 8、3。下图中用浅绿色标出,黄色代表其祖先节点。





下面,我们来分析一下节点 8、3 怎么得来的。



  • 节点 8 :其父节点 2 与目标节点 5 的距离为 1,因此只需要往左边分支找到与节点 2 距离为 2 的节点。

  • 节点 3:其父节点 1 与目标节点 5 的距离为 2,因此只需要往右边分支上找到与节点 1 距离为 1 的节点。



思路梳理



通过对栗子结果进行分析,我们可以确定节点的寻找方向:

  • 目标节点的子节点,往下找。

  • 目标节点所有祖先节点的子节点。先往上找到祖先节点后,再找各祖先节点的子树,即往下找。



如何找到目标节点的祖先节点?简单,只需要计算出从根节点到目标节点的路径,记录下来。



计算出其祖先节点后,怎样找到与其距离为 K 的节点呢?



  • 直接父节点,记为 p1

1. 如果目标节点是 p1 的左子树,那么只需要从 p1 的右节点开始遍历,找到与右节点距离为 K - 2 的所有节点;



2. 如果目标节点是 p1 的右子树,那么只需要从 p1 的左节点开始遍历,找到与左节点距离为 K - 2 的所有节点。



也就是说,从父节点的另一个子树开始找起。这就需要我们在计算路径的时候,记下节点方向,是左还是右节点。



为什么是 K -2 ?因为父节点与目标节点距离为 1,父节点与另一方向子节点距离也为 1



这样就全部转换为向下查找:求从某节点开始,与其距离为 K-2 的所有子节点集合。而这种查找方式比较简单。



  • 倒数第二个父节点,记为 p2



推论同上,只不过距离为 K - 3

...

以此类推。



很显然,这需要知道祖先节点与目标节点的距离。



而当我们以数组记录节点路径时(不包括目标节点),自然可以得出某节点与目标节点的距离。



比如路径为 paths = [A, B, C]。则 A 与目标节点的距离为 paths.lengthC 与其距离为 paths.length - 1B 与其距离为 paths.length - 2



以上我们只是计算了以父节点另一分支开始的情况,而从它自身开始的节点也需要考虑。



从上述的分析中,将所要做的步骤分解如下:

  1. 计算从根节点到目标节点路径,并记录各个节点方向。

  2. 依次遍历各祖先节点,计算出以另一子节点开始,距离为 n 的所有节点,n 跟祖先节点位置有关。注意如果某父节点与其距离刚好是 K,则不需要计算子节点了。

  3. 计算以目标节点开始,与其距离为 K 的节点。



这样,就可求出所有距离为 K 的节点。



代码实现



下面给出关键性代码。



  1. 寻找节点路径。



// 找到 root -> target 之间的路径,不包括 target
var getPath = function (root, target) {
if (root) {
if (root == target) {
return []
} else {
let result1 = null
let result2 = null

// 左边是否存在节点
if (root.left) {
result1 = getPath(root.left, target)
}
// 右边是否存在节点
if (root.right) {
result2 = getPath(root.right, target)
}

if (result1) {
// 0 代表左边节点
const curNode = { node: root, dir: 0 }
return [curNode].concat(result1)
} else if (result2) {
// 1 代表右边节点
const curNode = { node: root, dir: 1 }
return [curNode].concat(result2)
}

// 都不存在
return null
}
}

return null
}



  1. 找出以某节点开始的,距离为 n 的所有节点。



// 以 node 开始的,长度为 totalDistance 的节点
var distance = function (node, curDistance, totalDistance) {

console.log(node.val, curDistance, totalDistance)
if (node) {
if (curDistance === totalDistance) {
return [node.val]
}

let result = []
if (node.left) {
const leftResult = distance(node.left, curDistance + 1, totalDistance)
result = result.concat(leftResult)
}

if (node.right) {
const rightResult = distance(node.right, curDistance + 1, totalDistance)
result = result.concat(rightResult)
}

return result
}

return []
}



完整代码可点此查看



解法 2



这种解法的思路在大体上差不多,但是没解法 1 那么复杂,因为它只需记录路径上的节点(包括目标节点)与目标节点的距离。

思路梳理



主要思路如下:

  • 计算出路径上的节点与目标节点的距离。

  • 计算树中每个节点与目标节点的距离,如果等于 K,则满足条件。

由于之前计算出了路径上节点的距离,可以直接获取。而往子节点遍历时只需要在其基础上 +1 即可。



可见思路之清晰,当看完代码后,会发现实现也很简洁。

结合栗子分析



以解法 1 中的栗子来看,路径上的节点 [1, 2, 5] 与目标节点距离的数据如下:



// 节点 2 与节点 5 的距离为 1
Key = 2, Value = 1

// 节点 5,与其自身距离为 0
Key = 5, Value = 0

// 节点 1 与节点 5 的距离为 2
Key = 1, Value = 2



树中每个节点与目标节点 6 的距离如下:

节点 1: 2
节点 2: 1
节点 4: 2
节点 8: 3
节点 5: 0
节点 9: 1
节点 3: 3
节点 6: 4
节点 7: 4



其中 1、2、5 为路径上的节点,可以看到更新为了正确的值。这就是从已计算的结果中取值。

代码实现



关键代码如下:

private void dfs(TreeNode root, int K, int length, List<Integer> res) {
if (root == null) return;

int tmp = length;

// 如果已记录,则使用已有值。很关键,特别是对于同分支方向的查找
if (map.containsKey(root)) tmp = map.get(root);

// 距离满足
if (tmp == K) res.add(root.val);

// 遍历子树,距离 + 1
dfs(root.left, K, tmp + 1, res);
dfs(root.right, K, tmp + 1, res);
}



完整代码可点此查看



通过对比两种解法,发现我的思路还是局限了些,老想着往祖先节点的另一分支上去找,所以才会需要记录节点的方向。而它这种方式,即使在祖先节点相同的分支找,根据已记录的节点距离,也会获取到与目标节点的真正距离,完全无需担心。



发布于: 2020 年 06 月 01 日 阅读数: 32
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
# LeetCode 863. All Nodes Distance K in Binary Tree