863. 二叉树中所有距离为 K 的结点
Difficulty
Medium
Tags
二叉树
图
Star
给定一个二叉树（具有根结点
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 注意，输入的 "root" 和 "target" 实际上是树上的结点。 上面的输入仅仅是对这些对象进行了序列化描述。
提示：
- 给定的树是非空的。
- 树上的每个结点都具有唯一的值
0 <= node.val <= 500。
- 目标结点
target是树上的结点。
0 <= K <= 1000.
法1 Build Graph + BFS
思路
- 根据树建立一个无向图
- 从
target开始遍历该无向图
- 收集所有满足条件的节点
实现
采用 HashTable来建图,代码如下：
def buildGraph(self, root): # 先建立 parent 和 child 的相互映射 if root.left: self.graph.setdefault(root.val,[]).append(root.left.val) self.graph.setdefault(root.left.val,[]).append(root.val) self.buildGraph(root.left) if root.right: self.graph.setdefault(root.val,[]).append(root.right.val) self.graph.setdefault(root.right.val,[]).append(root.val) self.buildGraph(root.right)
或者如下
def buildGraph(self, parent, child): # 先建立 parent 和 child 的相互映射 if parent: self.graph.setdefault(parent.val,[]).append(child.val) self.graph.setdefault(child.val,[]).append(parent.val) # 再去递归建立子节点 if child.left: self.buildGraph(child, child.left) if child.right: self.buildGraph(child, child.right)
BFS遍历树
建立两个容器，一个用来存放已遍历节点，另外一个为队列，辅助BFS。代码如下：
seen = [] # 存放遍历过的节点,只进不出 queue = [] # 辅助bfs的队列 queue.append(target.val) seen.append(target.val) count = 0 while len(queue) > 0 and count <= k: size = len(queue) print(f"size:{size}, queue:{queue}") while size > 0: node = queue.pop(0) print(f"size:{size},node:{node}") size -= 1 if count == k: print(node) self.res.append(node) for childNode in self.graph[node]: if childNode not in seen: queue.append(childNode) seen.append(childNode) count += 1 return self.res
题解
# 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]: # 建图 self.graph = collections.defaultdict(list) self.build_graph(root) # 用 bfs 查找 queue = deque() visited = set() queue.append(target.val) visited.add(target.val) while queue: if k == 0: return list(queue) k -= 1 temp_size = len(queue) while temp_size > 0: cur_val = queue.popleft() temp_size -= 1 for val in self.graph[cur_val]: if val not in visited: queue.append(val) visited.add(val) return [] def build_graph(self, root): if root is None: return if root.left: self.graph[root.val].append(root.left.val) self.graph[root.left.val].append(root.val) self.build_graph(root.left) if root.right: self.graph[root.val].append(root.right.val) self.graph[root.right.val].append(root.val) self.build_graph(root.right)
法2 递归
思路
对每个节点计算，从当前节点到target节点的距离：
- 如果距离大于1，说明在当前节点的左子树或右子树。
- 如果距离为-1，表示target不再子树内
题解
# 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]: self.res= [] self.distance(node=root, target=target, k=k) return self.res def distance(self, node, target, k): if node is None: return -1 if node == target: self.collect(target,k) return 0 l = self.distance(node.left, target, k) r = self.distance(node.right, target, k) # target在左子树 if l >= 0: if l == k-1: self.res.append(node.val) # 在右子树收集 距离root.right为k-l-2的节点 self.collect(node.right, k-l-2) return l+1 # target在右子树 if r >= 0: if r == k-1: self.res.append(node.val) self.collect(node.left, k-r-2) return r+1 return -1 # 收集距离node节点k步的节点 def collect(self, node, k): if node is None or k < 0 : return if k == 0: self.res.append(node.val) self.collect(node.left, k-1) self.collect(node.right, k-1)