二叉树中所有距离为 K 的结点
题解
首先分析题意的：
1.第一步：按照 根->左->右 构建二叉树
2.第二步：找到特定结点
3.第三步：标记路径结点长度。得出结果
思路：
利用map标记从root到target的路径上的每个结点的traget值。如在本题中mp[target]=0,mp[root]=1,
mp[1] = 2;路径上没有其他结点，就从根节点开始搜索，遇到之前路径上的结点，就修改当前已经记录的路径长度。
class Solution {
private:
unordered_map<TreeNode*,int> mp;
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
vector<int> ans;
if(root==NULL) return ans;
findPath(root, target);
dfs(root,target,K,mp[root],ans); //使用dfs进行搜索
return ans;
}
int findPath(TreeNode* root, TreeNode* target){//利用map存储从root到target的路径长度
if(root==NULL) return -1;
if(root==target){
mp[root]=0;
return 0;
}
int left=findPath(root->left,target);
if(left>=0){
mp[root]=left+1;
return left+1;
}
int right=findPath(root->right,target);
if(right>=0){
mp[root]=right+1;
return right+1;
}
return -1;
}
void dfs(TreeNode *root,TreeNode* target, int K,int length,vector<int> &ans){
if(root==NULL) return;
if(mp.count(root)) length=mp[root];//如果在root到target的路径上，就更换为原来的路径，注意这里不能用mp[root]==0来判断，一来这种操作本身很危险，其次因为mp[target]=0会把target的情况忽略掉..
if(K==length) ans.push_back(root->val);
dfs(root->left,target,K,length+1,ans);
dfs(root->right,target,K,length+1,ans);
}
};
