LeetCode 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
注意，输入的 “root” 和 “target” 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
提示：
给定的树是非空的，且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0<=k<=1000
算法分析
由题意我们知道每个节点的值是独一无二的。但是二叉树是单向搜索的，即没法知道一个节点的父亲节点。这就需要我们想办法把一个节点的父亲节点找到。
我们用一个map来存储一个节点的父亲节点。然后定义一个vector里面存储访问过的节点。当需要对一个节点进行计算的时候，那么把这个节点进行是否访问的检测。没访问过就执行计算距离的运算。否则不执行。
代码如下：
#include
#include

return node;

}
map<int, treeNode*> parentMap;
void fillparentMap(treeNode *node)//记录各个节点的父亲节点。不需要记录root的父亲节点
{
if (node->lChild)
{
parentMap[node->lChild->val] = node;
fillparentMap(node->lChild);
}
if (node->rChild)
{
parentMap[node->rChild->val] = node;
fillparentMap(node->rChild);
}
}
vector dk;//记录距离为K的节点
vector visited;//记录已经访问过的节点
bool isVisted(int k)
{
auto iter = std::find(visited.begin(), visited.end(), k);//查找K是否已经访问过了
if (iter != visited.end())
{
return true;
}
return false;
}
void calcatNode(treeNode *node, int k, int distance)
{
visited.push_back(node->val);
if (k == distance)//当k==distance 的时候，把该节点的值加入dk。
{
dk.push_back(node->val);
}
else
{
if (node->lChild)//存在左节点，判断左节点是否遍历，再计算左节点，距离+1
{
if (!isVisted(node->lChild->val))
{
calcatNode(node->lChild, k+1, distance);
}
}
if (node->rChild)//存在右节点，判断右节点是否遍历，再计算右节点，距离+1
{
if (!isVisted(node->rChild->val))
{
calcatNode(node->rChild, k+1, distance);
}
}
if (parentMap[node->val])//存在父亲节点，判断父亲节点是否遍历，再计算右节点，距离+1
{
if (!isVisted(parentMap[node->val]->val))
{
calcatNode(parentMap[node->val], k+1, distance);
}
}
}
}
void calcatDistanceK(int target, int distance)
{
auto parent = parentMap[target];
treeNode *targetNode = nullptr;
if (parent->lChild->val == target)
{
targetNode = parent->lChild;
}
else
{
targetNode = parent->rChild;
}
visited.push_back(target);
int k = 0;
if (targetNode->lChild)
{
if (!isVisted(targetNode->lChild->val))
{
calcatNode(targetNode->lChild, 1, distance);
}
}
if (targetNode->rChild)
{
if (!isVisted(targetNode->rChild->val))
{
calcatNode(targetNode->rChild, 1, distance);
}
}
if (parentMap[target])
{
if (!isVisted(parentMap[target]->val))
{
calcatNode(parentMap[target], 1, distance);
}
}
}
int main()
{
//srand((unsigned)time(NULL));
int intarr[11] = { 3,5,1,6,2,0,8,-1,-1,7,4 };
treeNode *root = createTree(intarr, 11, 0);
fillparentMap(root);
calcatDistanceK(5,3);
for (auto x : dk)
{
cout << x << endl;
}
dk.clear();//进行新的计算的时候的，记得清空两个全局变量。
visited.clear();
cout << endl;
calcatDistanceK(5, 2);
for (auto x : dk)
{
cout << x << endl;
}
system(“pause”);

return 0;

}
执行结果：