友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
863. 二叉树中所有距离为 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
示例 2:
输入: root = [1], target = 1, k = 3 输出: []
提示:
-
节点数在
[1, 500]范围内 -
0 <= Node.val <= 500 -
Node.val中所有值 不同 -
目标结点
target是树上的结点。 -
0 <= k <= 1000
思路分析
先找出从根节点到目标节点之间的路径。再根据这个路径去做深度优先搜索，找到符合要求的节点。
| 看了一圈题解，感觉我的题解最简洁。 |
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-14 22:42:21
*/
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> result = new ArrayList<>();
List<TreeNode> path = findPath(root, target);
for (int i = 0; i <= Math.min(path.size() - 1, k); i++) {
dfs(path.get(i), result, k, i, path);
}
return result;
}
private List<TreeNode> findPath(TreeNode root, TreeNode target) {
if (root == null) {
return null;
}
if (root.val == target.val) {
return new ArrayList<>(List.of(root));
}
List<TreeNode> left = findPath(root.left, target);
if (left != null) {
left.add(root);
return left;
}
List<TreeNode> right = findPath(root.right, target);
if (right != null) {
right.add(root);
return right;
}
return null;
}
private void dfs(TreeNode root, List<Integer> result,
int k, int depth, List<TreeNode> path) {
if (root == null) {
return;
}
if (depth == k) {
result.add(root.val);
return;
}
if (!path.contains(root.left)) {
dfs(root.left, result, k, depth + 1, path);
}
if (!path.contains(root.right)) {
dfs(root.right, result, k, depth + 1, path);
}
}