863. 二叉树中所有距离为 K 的结点
给定一个二叉树（具有根结点 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
输出: []
提示:
节点数在 [1, 500] 范围内
0 <= Node.val <= 500
Node.val 中所有值 不同
目标结点 target 是树上的结点。
0 <= k <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
DFS
返回距离目标target为k的所有结点，显然不是最短路径问题，只能用dfs，我们知道二叉树是特殊的图，因此可以对二叉树的那个结点进行dfs，但最大的问题就是二叉树可以对左孩子和右孩子进行遍历，但是对父节点进行进行遍历很麻烦，所以我们要用一个容器缓存结点的父节点，即map【由题目可知结点的值唯一，因此可以用值作为哈希的键】。
初始化好map之后就可以用dfs算法对target结点开始父节点 左孩子，右孩子进行dfs访问，为了防止重复访问要设置一个visit数组访问过得结点设置访问标志。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
map<int, TreeNode*> parent;
TreeNode* pre;
bool visit[501];
vector<int> res;
void initParent(TreeNode* node) {
if(node == NULL){
return;
}
parent[node->val] = pre;
pre = node;
initParent(node->left);
pre = node;
initParent(node->right);
}
void dfs(TreeNode* node, int k){
if(node == NULL){
return;
} else if(visit[node->val]){
return;
}
visit[node->val] = true;
if(k == 0){
res.push_back(node->val);
return;
} else if(k < 0){
return;
}
// 上
if(parent[node->val]){
dfs(parent[node->val], k - 1);
}
// 左
dfs(node->left, k - 1);
// 右
dfs(node->right, k - 1);
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
memset(visit, false, sizeof(visit));
initParent(root);
dfs(target, k);
return res;
}
};
