给定一个二叉树（具有根结点
root）， 一个目标结点target，和一个整数值k。返回到目标结点
target距离小于等于k的所有结点的值的列表。 答案可以以 任何顺序 返回。
class Solution:
def __init__(self, data):
self.data = data
self.result = set()
def distance_k(self, target, k):
if not self.data: return
self.process(target, k)
return self.result
def process(self, index, k):
if k < 0 or not self.data[index]: return self.result
self.result.add(index)
left = self.get_left(index)
right = self.get_right(index)
parent = self.get_parent(index)
if left < len(self.data):
self.process(left, k - 1)
if right < len(self.data):
self.process(right, k - 1)
if parent >= 0:
self.process(parent, k - 1)
return self.result
def get_left(self, index):
return 2 * index + 1
def get_right(self, index):
return 2 * (index + 1)
def get_parent(self, index):
return int((index - 1) / 2)
扩展
给定一个二叉树（具有根结点
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
输出: []
class Solution:
def __init__(self, data):
self.data = data
self.seen = set()
self.result = set()
def distance_k(self, target, k):
if not self.data: return
self.process(target, k)
return self.result
def process(self, index, k):
if k < 0 or index in self.seen: return self.result
self.seen.add(index)
if k == 0: self.result.add(index)
left = self.get_left(index)
right = self.get_right(index)
parent = self.get_parent(index)
if left < len(self.data):
self.process(left, k - 1)
if right < len(self.data):
self.process(right, k - 1)
if parent >= 0:
self.process(parent, k - 1)
return self.result
def get_left(self, index):
return 2 * index + 1
def get_right(self, index):
return 2 * (index + 1)
def get_parent(self, index):
return int((index - 1) / 2)
solution = Solution([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
print(solution.distance_k(4, 2))