@(LeetCode)
问题描述
给定一颗二叉树的根节点 root，目标节点 target，和一个整数 K。
返回与目标节点距离为 K 的节点列表，顺序随意。
栗 1：
image.png
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
树的结构如上图所示。与节点 5 的距离为 2 的节点有：7、4、1。
注意：
- 二叉树非空。
- 每个节点值都是唯一的，范围在
[0, 500]。 -
target节点在树中。 -
0 <= K <= 1000。
解题思路
解法 1
解法 1 也是我自己的解法。
初看这题，我冒出的想法是：计算目标节点所在的层，然后再往下数 K 层，则该层上的所有节点与其距离肯定为 K。
但是，又回头看了看栗子，发现没那么简单。其不仅仅包括目标节点的子节点 7、4，而且还包括其兄弟节点 1，也可认为是其父节点的子节点。
栗子分析
先看一个复杂些的栗子，树结构如下图所示。其中 K = 3，红色代表目标节点 5。
image.png
我们从图中可以看出，与其距离为 3 的节点包括 8、3。下图中用浅绿色标出，黄色代表其祖先节点。
下面，我们来分析一下节点 8、3 怎么得来的。
- 节点
8：其父节点2与目标节点5的距离为1，因此只需要往左边分支找到与节点2距离为2的节点。 - 节点
3：其父节点1与目标节点5的距离为2，因此只需要往右边分支上找到与节点1距离为1的节点。
思路梳理
通过对栗子结果进行分析，我们可以确定节点的寻找方向：
- 目标节点的子节点，往下找。
- 目标节点所有祖先节点的子节点。先往上找到祖先节点后，再找各祖先节点的子树，即往下找。
如何找到目标节点的祖先节点？简单，只需要计算出从根节点到目标节点的路径，记录下来。
计算出其祖先节点后，怎样找到与其距离为 K 的节点呢？
-
直接父节点，记为
p1。-
如果目标节点是
p1的左子树，那么只需要从p1的右节点开始遍历，找到与右节点距离为K - 2的所有节点； -
如果目标节点是
p1的右子树，那么只需要从p1的左节点开始遍历，找到与左节点距离为K - 2的所有节点。
也就是说，从父节点的另一个子树开始找起。这就需要我们在计算路径的时候，记下节点方向，是左还是右节点。
为什么是
K -2？因为父节点与目标节点距离为1，父节点与另一方向子节点距离也为1。这样就全部转换为向下查找：求从某节点开始，与其距离为
K-2的所有子节点集合。而这种查找方式比较简单。 -
-
倒数第二个父节点，记为
p2。
推论同上，只不过距离为 K - 3。
...
以此类推。
很显然，这需要知道祖先节点与目标节点的距离。
而当我们以数组记录节点路径时（不包括目标节点），自然可以得出某节点与目标节点的距离。
比如路径为 paths = [A, B, C]。则 A 与目标节点的距离为 paths.length，C 与其距离为 paths.length - 1，B 与其距离为 paths.length - 2。
以上我们只是计算了以父节点另一分支开始的情况，而从它自身开始的节点也需要考虑。
从上述的分析中，将所要做的步骤分解如下：
- 计算从根节点到目标节点路径，并记录各个节点方向。
- 依次遍历各祖先节点，计算出以另一子节点开始，距离为
n的所有节点，n跟祖先节点位置有关。注意如果某父节点与其距离刚好是K，则不需要计算子节点了。 - 计算以目标节点开始，与其距离为
K的节点。
这样，就可求出所有距离为 K 的节点。
代码实现
下面给出关键性代码。
- 寻找节点路径。
// 找到 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
}
- 找出以某节点开始的，距离为
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);
}
通过对比两种解法，发现我的思路还是局限了些，老想着往祖先节点的另一分支上去找，所以才会需要记录节点的方向。而它这种方式，即使在祖先节点相同的分支找，根据已记录的节点距离，也会获取到与目标节点的真正距离，完全无需担心。
网友评论