# # 【LeetCode】863. All Nodes Distance K in Binary Tree 解题报告（Python）

## # 题目描述：

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Example 1:

``````Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation:
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.
``````

``````Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.
``````

Note:

1. The given tree is non-empty.
2. Each node in the tree has unique values 0 <= node.val <= 500.
3. The target node is a node in the tree.
4. 0 <= K <= 1000.

## # 解题方法

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def distanceK(self, root, target, K):
"""
:type root: TreeNode
:type target: TreeNode
:type K: int
:rtype: List[int]
"""
# DFS
conn = collections.defaultdict(list)
def connect(parent, child):
if parent and child:
conn[parent.val].append(child.val)
conn[child.val].append(parent.val)
if child.left: connect(child, child.left)
if child.right: connect(child, child.right)
connect(None, root)
# BFS
que = collections.deque()
que.append(target.val)
visited = set([target.val])
for k in range(K):
size = len(que)
for i in range(size):
node = que.popleft()
for j in conn[node]:
if j not in visited:
que.append(j)
return list(que)
``````

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def distanceK(self, root, target, K):
"""
:type root: TreeNode
:type target: TreeNode
:type K: int
:rtype: List[int]
"""
# DFS
conn = collections.defaultdict(list)
def connect(parent, child):
if parent and child:
conn[parent.val].append(child.val)
conn[child.val].append(parent.val)
if child.left: connect(child, child.left)
if child.right: connect(child, child.right)
connect(None, root)
# BFS
bfs = [target.val]
visited = set([target.val])
for k in range(K):
bfs = [y for x in bfs for y in conn[x] if y not in visited]
visited |= set(bfs)
return bfs
``````

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143729/Python-DFS-and-BFS/175740

## # 日期

2018 年 9 月 14 日 ———— 现在需要的还是夯实基础，算法和理论