LeetCode 863. 二叉树中所有距离为 K 的结点
题目描述
思路分析
解法一：建父节点映射 + BFS（推荐）
核心思路：
- 二叉树只有从父节点到子节点的单向边，无法直接从子节点向上查找。
- 第一步：通过 DFS 遍历整棵树，用哈希表记录每个节点的父节点，将树转化为无向图。
- 第二步：从目标节点
target出发，做 BFS 多源扩展，同时访问左子节点、右子节点和父节点三个方向。- 第三步：BFS 扩展到第 K 层时，队列中所有节点即为答案。
- 使用 visited 集合避免重复访问同一节点。
复杂度分析：
- 时间复杂度：O(n)，其中 n 表示二叉树的节点数，DFS 建图和 BFS 搜索均为 O(n)。
- 空间复杂度：O(n)，其中 n 表示二叉树的节点数，哈希表、队列、visited 集合空间均为 O(n)。
class Solution {
// 记录每个节点的父节点
private Map<Integer, TreeNode> parentMap = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
// DFS 建立父节点映射
buildParentMap(root, null);
List<Integer> result = new ArrayList<>();
// visited 集合避免重复访问
Set<Integer> visited = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(target);
visited.add(target.val);
int distance = 0;
while (!queue.isEmpty()) {
// 当前层节点数
int size = queue.size();
if (distance == k) {
// 当前层即为距离 K 的所有节点
for (TreeNode node : queue) {
result.add(node.val);
}
return result;
}
// 扩展下一层：左子节点、右子节点、父节点
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
if (curr.left != null && !visited.contains(curr.left.val)) {
visited.add(curr.left.val);
queue.offer(curr.left);
}
if (curr.right != null && !visited.contains(curr.right.val)) {
visited.add(curr.right.val);
queue.offer(curr.right);
}
TreeNode parent = parentMap.get(curr.val);
if (parent != null && !visited.contains(parent.val)) {
visited.add(parent.val);
queue.offer(parent);
}
}
distance++;
}
return result;
}
// DFS 遍历建立父节点映射
private void buildParentMap(TreeNode node, TreeNode parent) {
if (node == null) {
return;
}
parentMap.put(node.val, parent);
buildParentMap(node.left, node);
buildParentMap(node.right, node);
}
}
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
// 记录每个节点的父节点
parentMap := make(map[int]*TreeNode)
// DFS 建立父节点映射
var buildParentMap func(node, parent *TreeNode)
buildParentMap = func(node, parent *TreeNode) {
if node == nil {
return
}
parentMap[node.Val] = parent
buildParentMap(node.Left, node)
buildParentMap(node.Right, node)
}
buildParentMap(root, nil)
result := []int{}
// visited 集合避免重复访问
visited := make(map[int]bool)
queue := []*TreeNode{target}
visited[target.Val] = true
distance := 0
for len(queue) > 0 {
// 当前层即为距离 K 的所有节点
if distance == k {
for _, node := range queue {
result = append(result, node.Val)
}
return result
}
size := len(queue)
// 扩展下一层：左子节点、右子节点、父节点
for i := 0; i < size; i++ {
curr := queue[i]
if curr.Left != nil && !visited[curr.Left.Val] {
visited[curr.Left.Val] = true
queue = append(queue, curr.Left)
}
if curr.Right != nil && !visited[curr.Right.Val] {
visited[curr.Right.Val] = true
queue = append(queue, curr.Right)
}
parent := parentMap[curr.Val]
if parent != nil && !visited[parent.Val] {
visited[parent.Val] = true
queue = append(queue, parent)
}
}
queue = queue[size:]
distance++
}
return result
}
解法二：DFS 递归
核心思路：
- 在 DFS 递归过程中，通过返回值传递当前节点与
target的距离信息。- 若在左子树中找到
target，则当前节点到target的距离为左子树返回值 +1；此时需要在右子树中搜索距离为k - dist - 1的节点（dist为当前节点到target的距离）。- 若当前节点即为
target，则在以当前节点为根的子树中，搜索深度为k的所有节点。- 通过
subtreeAdd辅助函数在以某节点为根的子树中，搜索距离根节点恰好为dist的所有节点。
复杂度分析：
- 时间复杂度：O(n)，其中 n 表示二叉树的节点数，每个节点最多被访问常数次。
- 空间复杂度：O(n)，其中 n 表示二叉树的节点数，递归栈深度最坏为 O(n)（退化为链表）。
class Solution {
private List<Integer> result = new ArrayList<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
dfs(root, target, k);
return result;
}
/**
* 返回当前节点到 target 的距离，若子树中不含 target 则返回 -1。
*/
private int dfs(TreeNode node, TreeNode target, int k) {
if (node == null) {
return -1;
}
if (node == target) {
// 当前节点即为 target，在其子树中搜索深度为 k 的节点
subtreeAdd(node, k);
return 0;
}
// 在左子树中搜索 target
int leftDist = dfs(node.left, target, k);
if (leftDist != -1) {
// 当前节点到 target 距离为 leftDist + 1
if (leftDist + 1 == k) {
result.add(node.val);
} else {
// 在右子树中搜索距离为 k - leftDist - 2 的节点
subtreeAdd(node.right, k - leftDist - 2);
}
return leftDist + 1;
}
// 在右子树中搜索 target
int rightDist = dfs(node.right, target, k);
if (rightDist != -1) {
// 当前节点到 target 距离为 rightDist + 1
if (rightDist + 1 == k) {
result.add(node.val);
} else {
// 在左子树中搜索距离为 k - rightDist - 2 的节点
subtreeAdd(node.left, k - rightDist - 2);
}
return rightDist + 1;
}
return -1;
}
/**
* 在以 node 为根的子树中，收集距离根恰好为 dist 的所有节点。
*/
private void subtreeAdd(TreeNode node, int dist) {
if (node == null || dist < 0) {
return;
}
if (dist == 0) {
result.add(node.val);
return;
}
subtreeAdd(node.left, dist - 1);
subtreeAdd(node.right, dist - 1);
}
}
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
result := []int{}
// subtreeAdd 在以 node 为根的子树中，收集距离根恰好为 dist 的所有节点
var subtreeAdd func(node *TreeNode, dist int)
subtreeAdd = func(node *TreeNode, dist int) {
if node == nil || dist < 0 {
return
}
if dist == 0 {
result = append(result, node.Val)
return
}
subtreeAdd(node.Left, dist-1)
subtreeAdd(node.Right, dist-1)
}
// dfs 返回当前节点到 target 的距离，若子树不含 target 则返回 -1
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return -1
}
// 当前节点即为 target，在其子树中搜索深度为 k 的节点
if node == target {
subtreeAdd(node, k)
return 0
}
// 在左子树中搜索 target
leftDist := dfs(node.Left)
if leftDist != -1 {
if leftDist+1 == k {
result = append(result, node.Val)
} else {
// 在右子树中搜索距离为 k - leftDist - 2 的节点
subtreeAdd(node.Right, k-leftDist-2)
}
return leftDist + 1
}
// 在右子树中搜索 target
rightDist := dfs(node.Right)
if rightDist != -1 {
if rightDist+1 == k {
result = append(result, node.Val)
} else {
// 在左子树中搜索距离为 k - rightDist - 2 的节点
subtreeAdd(node.Left, k-rightDist-2)
}
return rightDist + 1
}
return -1
}
dfs(root)
return result
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | BFS / 层序遍历 |
| 1026. 节点与其祖先之间的最大差值 | 中等 | 二叉树 / DFS |
| 1123. 最深叶节点的最近公共祖先 | 中等 | 二叉树 / DFS |
| 1376. 通知所有员工所需的时间 | 中等 | 树 / DFS / BFS |
| 199. 二叉树的右视图 | 中等 | BFS / DFS |
| 236. 二叉树的最近公共祖先 | 中等 | 二叉树 / DFS / 递归 |
| 1110. 删点成林 | 中等 | 二叉树 / DFS / 哈希表 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！