LeetCode 题解工作台
二叉树中所有距离为 K 的结点
给定一个二叉树（具有根结点 root ）， 一个目标结点 target ，和一个整数值 k ，返回到目标结点 target 距离为 k 的所有结点的值的数组。 答案可以以 任何顺序 返回。 示例 1： 输入： root = [3,5,1,6,2,0,8,null,null,7,4], target …
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们先用 DFS 遍历整棵树，将每个节点的父节点保存到哈希表 中。 接下来，我们再次用 DFS，从 出发，向上向下搜索距离为 的节点，添加到结果数组中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树（具有根结点 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 <= 500Node.val中所有值 不同- 目标结点
target是树上的结点。 0 <= k <= 1000
解题思路
方法一：DFS + 哈希表
我们先用 DFS 遍历整棵树，将每个节点的父节点保存到哈希表 中。
接下来，我们再次用 DFS，从 出发，向上向下搜索距离为 的节点，添加到结果数组中。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
def dfs(root, fa):
if root is None:
return
g[root] = fa
dfs(root.left, root)
dfs(root.right, root)
def dfs2(root, fa, k):
if root is None:
return
if k == 0:
ans.append(root.val)
return
for nxt in (root.left, root.right, g[root]):
if nxt != fa:
dfs2(nxt, root, k - 1)
g = {}
dfs(root, None)
ans = []
dfs2(target, None, k)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate familiarity with tree traversal methods such as DFS and BFS.
- question_mark
Be aware of the candidate's ability to handle edge cases, especially small trees or large K values.
- question_mark
Look for candidates who suggest methods for efficiently tracking distances, using a hash map or other techniques.
常见陷阱
外企场景- error
Forgetting to account for both upward and downward traversals when calculating distances from the target.
- error
Not handling cases where K is larger than the height of the tree, which results in empty output.
- error
Misusing the BFS or DFS traversal, leading to inefficient or incorrect traversal of the tree.
进阶变体
外企场景- arrow_right_alt
Modify the problem to find all nodes within a range [L, R] of distances from the target node.
- arrow_right_alt
Implement the solution using an iterative DFS approach instead of recursive DFS.
- arrow_right_alt
Extend the problem to handle binary search trees (BST) where additional properties can be used for optimization.