题解 | #距离是K的二叉树节点#
距离是K的二叉树节点
http://www.nowcoder.com/practice/e280b9b5aabd42c9b36831e522485622
class Solution {
public:
unordered_map<int,TreeNode*>parent;
vector<int>ans;
TreeNode* t;
void findParent(TreeNode* root)
{
if(root->left)
{
parent[root->left->val]=root;
findParent(root->left);
}
if(root->right)
{
parent[root->right->val]=root;
findParent(root->right);
}
}
void findAns(TreeNode* root,TreeNode* from,int d,int k)
{
if(!root)
return;
if(d==k)
{
ans.emplace_back(root->val);
return;
}
if(root->left!=from)
findAns(root->left,root,d+1,k);
if(root->right!=from)
findAns(root->right,root,d+1,k);
if(parent[root->val]!=from)
findAns(parent[root->val],root,d+1,k);
}
void findTarget(TreeNode* root,int target)
{
if(!root)
return;
findTarget(root->left,target);
findTarget(root->right,target);
if(root->val==target)
{
t=root;
return;
}
}
vector<int> distanceKnodes(TreeNode* root, int target, int k) {
findParent(root);
findTarget(root,target);
findAns(t,NULL,0,k);
return ans;
}
};
