863. 二叉树中所有距离为 K 的结点

863. 二叉树中所有距离为 K 的结点

---

C代码：dfs

/**
 * 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83