关于#c/c++#的问题：二叉搜索树求所有到根节点距离为k的叶子节点没有头绪

C++数据结构，我现在已经完成了建树，但对于如何实现：求所有到根节点距离为k的叶子节点没有头绪，请问如何实现呢？

img

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int Datatype;
//定义二叉树结构体
typedef struct BSTNode{
    Datatype data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BiTree;

//二叉搜索树插入函数
int BST_Insert(BiTree &T, Datatype elem)
{
    BiTree TreeNew = (BiTree) calloc(1, sizeof(BSTNode));//新结点申请空间
    TreeNew->data = elem;//把结点值放入
    if(NULL == T)//如果树根为空就把新结点赋值给树根
    {
        T = TreeNew;
        return 1;
    }

    BiTree p = T, parent;
    while(p)
    {
        parent = p;
        if(elem > p->data)
        {
            p = p->rchild;
        } else if(elem < p->data)
        {
            p = p->lchild;
        } else
        {
            return 0;
        }
    }

    if(elem > parent->data)
    {
        parent->rchild = TreeNew;
    } else{
        parent->lchild = TreeNew;
    }
    return 1;
}

void Creat_BST(BiTree &T, Datatype* str, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        BST_Insert(T, str[i]);
    }
}

int main() {
    BiTree T = NULL;
    int i, len, k;
    printf("Please input the number of nodes\n");
    scanf("%d", &len);
    Datatype *str = (Datatype*) malloc(len * sizeof(Datatype));
    for (i=0;i<len;i++)
    {
        scanf("%d", &str[i]);
    }
    Creat_BST(T,str,len);
    printf("\n");

    scanf("%d", &k);

    return 0;
}

在下述代码中，getSumOfLeafNodesAtDepthKHelper() 方法和之前的代码示例相同，用于计算所有到根节点距离为k的叶子节点的值之和。在主函数中，我们先构造二叉搜索树，然后从控制台输入k的值，最后调用 getSumOfLeafNodesAtDepthKHelper() 方法计算结果并输出。

//计算所有到根节点距离为k的叶子节点的值之和
int getSumOfLeafNodesAtDepthKHelper(BiTree node, int k) {
  if (node == NULL) {
    return 0;
  }
  if (k == 0) {
    if (node->lchild == NULL && node->rchild == NULL) {
      return node->data;
    } else {
      return 0;
    }
  } else {
    return getSumOfLeafNodesAtDepthKHelper(node->lchild, k-1) + getSumOfLeafNodesAtDepthKHelper(node->rchild, k-1);
  }
}

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢