二叉树中所有距离为k的节点

题目链接：. - 力扣（LeetCode）

思路：  从目标节点的左孩子，右孩子，父亲节点出发去找，左孩子 右孩子 做法简单 ， 主要是父亲节点 ，因此我们需要知道每个节点的父亲节点，  题目中提示说所有值不同，因此我们存储该节点的父亲节点，可以用该节点的值作为下标

写一个函数：需要注意根节点没有父亲节点

void Find(struct TreeNode** parent , struct TreeNode* root)

 {

    if( root->left )

    {

        parent[root->left->val] = root;

        Find(parent,root->left);

    }

    if( root->right)

    {

        parent[root->right->val] = root;

        Find(parent,root->right);

    }

 }

然后从左孩子，右孩子，父亲节点找相应的距离节点

还需注意，已经访问的节点不可再次访问

因此要写一个数组，记录哪些节点已访问

写出下列代码：

 void test( int* arr,int* size,int k , int t,struct TreeNode* root,int* flag,struct TreeNode** parent,struct TreeNode* p)

 {

    if( t == k )

     {

    arr[(*size)++] = root->val;

    return;

     }

    if( root->left &&  flag[root->left->val] == 0 )

    {

        flag[root->left->val] = 1;

        test(arr,size,k,t+1,root->left,flag,parent,p);

    }

    if( root->right && flag[root->right->val] == 0 )

    {

        flag[root->right->val] = 1;

        test(arr,size,k,t+1,root->right,flag,parent,p);

    }

    if( root != p  && flag[(parent[root->val])->val] == 0 )//由于根节点没有父亲节点，因此要特殊判断

    {

        flag[parent[root->val]->val] = 1;

        test(arr,size,k,t+1,parent[root->val],flag,parent,p);

    }

   

 }

总代码：

  void Find(struct TreeNode** parent , struct TreeNode* root)

 {

   // if( !root )return;

    if( root->left )

    {

        parent[root->left->val] = root;

        Find(parent,root->left);

    }

    if( root->right)

    {

        parent[root->right->val] = root;

        Find(parent,root->right);

    }

 }

 void test( int* arr,int* size,int k , int t,struct TreeNode* root,int* flag,struct TreeNode** parent,struct TreeNode* p)

 {

    if( t == k )

     {

    arr[(*size)++] = root->val;

    return;

     }

    if( root->left &&  flag[root->left->val] == 0 )

    {

        flag[root->left->val] = 1;

        test(arr,size,k,t+1,root->left,flag,parent,p);

    }

    if( root->right && flag[root->right->val] == 0 )

    {

        flag[root->right->val] = 1;

        test(arr,size,k,t+1,root->right,flag,parent,p);

    }

    if( root != p  && flag[(parent[root->val])->val] == 0 )

    {

        flag[parent[root->val]->val] = 1;

        test(arr,size,k,t+1,parent[root->val],flag,parent,p);

    }

   

 }

int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize) {

    struct TreeNode** parent = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*505);

    Find(parent,root);

    int* arr = (int*)calloc(505,sizeof(int));

    int* flag = (int*)calloc(505,sizeof(int));

    flag[target->val] = 1;

    test(arr,returnSize,k,0,target,flag,parent,root);

    return arr;

}