863. All Nodes Distance K in Binary Tree
tree bfs dfs
Last updated
Was this helpful?
tree bfs dfs
Last updated
Was this helpful?
Given the root
of a binary tree, the value of a target node target
, and an integer k
, return an array of the values of all nodes that have a distance k
from the target node.
You can return the answer in any order.
Example 1:
Example 2:
Constraints:
The number of nodes in the tree is in the range [1, 500]
.
0 <= Node.val <= 500
All the values Node.val
are unique.
target
is the value of one of the nodes in the tree.
0 <= k <= 1000
分析
建立父节点映射:由于二叉树节点没有指向父节点的指针,我们首先需要遍历整棵树,记录每个节点的父节点,以便后续能够向上遍历。
广度优先搜索(BFS):从目标节点target
开始进行BFS,逐层向外扩展。每次处理当前层的节点时,检查其左子节点、右子节点和父节点,确保每个节点只访问一次。当距离达到k
时,收集当前层的所有节点。