863. 二叉树中所有距离为 K 的结点
文章来源:https://www.toymoban.com/news/detail-698814.html
C代码:dfs文章来源地址https://www.toymoban.com/news/detail-698814.html
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
typedef struct {
int key;
struct TreeNode* node;
UT_hash_handle hh;
} HashTable;
HashTable* head;
int* ans;
int ansSize;
void addToHash(int ikey, struct TreeNode* node) {
HashTable* out = NULL;
HASH_FIND_INT(head, &ikey, out); // 去找当前值的父节点
if (out == NULL) {
out = (HashTable*)malloc(sizeof(HashTable));
out->key = ikey;
out->node = node; // 保存当前节点的父节点
HASH_ADD_INT(head, key, out);
} else {
out->node = node;
}
}
void findParents(struct TreeNode* root) {
if (root->left != NULL) {
addToHash(root->left->val, root);
findParents(root->left);
}
if (root->right != NULL) {
addToHash(root->right->val, root);
findParents(root->right);
}
}
struct TreeNode* query(int ikey) {
HashTable* out = NULL;
HASH_FIND_INT(head, &ikey, out);
if (out == NULL) {
return NULL;
}
return out->node;
}
// 从target节点往3个方向搜索,确保3个方向的途经点不能再dfs回去!
void findAns(struct TreeNode* node, struct TreeNode* from, int depth, int k) {
if (node == NULL) {
return;
}
if (depth == k) { // 前序处理
ans[ansSize++] = node->val;
return;
}
if (node->left != from) { // 搜索左右子节点,from是途径过的上一个结点
findAns(node->left, node, depth + 1, k);
}
if (node->right != from) {
findAns(node->right, node, depth + 1, k);
}
if (query(node->val) != from) { // 顺着父节点往上搜索,node的父节点不等于from
findAns(query(node->val), node, depth + 1, k);
}
}
int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize) {
head = NULL; // target是个结点
ans = (int*)malloc(sizeof(int) * 500);
ansSize = 0;
findParents(root); // 从root出发 DFS,记录每个结点的父结点
findAns(target, NULL, 0, k); // 从target出发 DFS,寻找所有深度为 k 的结点
*returnSize = ansSize;
return ans;
}
到了这里,关于863. 二叉树中所有距离为 K 的结点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!