leetcode 863
Published:
题目863
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
输入样例
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2 输出：[7,4,1] 解释： 所求结点为与目标结点（值为 5）距离为 2 的结点， 值分别为 7，4，以及 1
解析
计算节点距离，最好还是在图上做，而二叉树也确实是一张特殊的图。而二叉树无法当作无向图搜索的问题就在于父子节点之间只存在单向。此时两种方案，要么把二叉树转换为邻接矩阵存储，要么转换为邻接表存储。
而邻接矩阵由于其稀疏性，很不合适，故使用邻接表存储。此时，每个点出度均为3（父节点、左子节点、右子节点），而这其中只有父子节点无法遍历到，故邻接矩阵可以进一步简化为存储从子节点到父节点的映射（leetcode最优解）。
形成图后，使用DFS或BFS搜索即可。
题解
按存储出度为3的邻接表方案实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import defaultdict
class Solution:
def search(self,fnode,curnode):
if curnode:
if fnode:
self.adj1[curnode.val].append(fnode.val)
if curnode.left:
lftson=curnode.left
self.adj1[curnode.val].append(lftson.val)
self.search(curnode,curnode.left)
if curnode.right:
rhtson=curnode.right
self.adj1[curnode.val].append(rhtson.val)
self.search(curnode,curnode.right)
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.adj1=defaultdict(list)
self.search(None,root)
nodeSign=[target.val]
curlist=[target.val]
nextlist=[]
result=[]
while k!=0:
for i in curlist:
for j in self.adj1[i]:
if j not in nodeSign:
nodeSign.append(j)
nextlist.append(j)
curlist=nextlist
nextlist=[]
k-=1
return curlist