1、描述
863给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2、关键字
二叉树、距离、
3、思路
target节点，向下就是层序遍历，只是向上就很难办，如果是图，就直接广度优先搜索就好了，所以把二叉树向上搜索的这一个方向：用map树转图，把当前节点入队列，然后当遍历到队列中的该节点时候，从该节点进行3个方向的搜索，左右子节点，父亲节点，
4、nodes
unordered_map<TreeNode *,TreeNode *> graph;
由子节点做key,父节点做val
用unordered_set<TreeNode *>visited;做标志有没有访问过
5、复杂度
时间：O（N）n是节点总书
空间：O（N)层序遍历就是这个值
6、code
/*** 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:vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {vector<int>res;// 定义结果集queue<TreeNode*>que; // 广度优先队列unordered_set<TreeNode*> visited; // 统计遍历过没有unordered_map<TreeNode*,TreeNode*> graph; // hash映射，子节点访问父节点的无向图if(K==0) // 特例{res.push_back(target->val);return res;}MakeMap(root,graph); //根据二叉树 构造无向图que.push(target);visited.insert(target); //标记已经访问int step=0;while(!que.empty()) // 外层循环{step++;int longth=que.size(); while(longth--) //内层循环{auto tem=que.front();que.pop();if(tem->left && !visited.count(tem->left)) // 队列中的元素，只有3个方向搜索，{if(step==K){res.push_back(tem->left->val);}que.push(tem->left);visited.insert(tem->left);}if(tem->right && !visited.count(tem->right)){if(step==K){res.push_back(tem->right->val);}que.push(tem->right);visited.insert(tem->right);}if(graph[tem] && !visited.count(graph[tem])) // 向父节点方向搜索，只搜索了一步而已，如果步数够，//就存res,不够就入队，然后当变成队首元素时候，再往3个方向搜索{if(step==K){res.push_back(graph[tem]->val);}que.push(graph[tem]);visited.insert(graph[tem]);}}if(step==K)break;}return res;}//树转无向图，打通根节点向父节点的搜索方向，void MakeMap(TreeNode * root,unordered_map<TreeNode*,TreeNode*> &umap){if(!root){return ;}//if(!root->left)if(root->left) // 有节点就下来{umap[root->left]=root;}//if(!root->right)if(root->right){umap[root->right]=root;}MakeMap(root->left,umap);MakeMap(root->right,umap);}
};