0863. All Nodes Distance K in Binary Tree¶
题目信息¶
- 题号:
0863
- 难度:
Medium
- 主题:
二叉树、节点距离、目标节点
- 原题:
- 重点:
target 是树中的目标节点;距离按无向路径边数计算,可以经过父节点,结果中的节点值顺序不限
题目重述¶
给定一棵二叉树的根节点 root、树中的目标节点 target 和非负整数 k。把父子连接视为可以双向经过的边,两个节点之间的距离等于它们唯一路径上的边数。
请返回所有与 target 距离恰好为 k 的节点值,结果顺序不限。题目中节点值互不相同,并保证目标节点确实属于该树。
树中节点数在 [1, 500] 范围内,节点值在 [0, 500] 范围内且互不相同,0 <= k <= 1000。
自建示例¶
答案同时来自父节点和子节点:
输入:树中 root = 1,节点 1 的左右孩子为 2、3,节点 2 的左右孩子为 4、5;target = 节点 2,k = 1
输出:[1,4,5]
解释:节点 2 的父节点 1 和两个孩子 4、5 都相距一条边;返回顺序可以不同。
距离为零:
输入:root = [7,3,9], target = 节点 3, k = 0
输出:[3]
解释:k 达到允许的最小值 0,只有目标节点本身与自己的距离为 0,因此结果只包含它的值 3。