二叉搜索树的第k个节点

[编程题]二叉搜索树的第k个节点

热度指数：54735 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

数据范围： $0 \le n \le1000$ ， $0 \le k \le1000$ ，树上每个结点的值满足 $0 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：

该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。

示例1

输入

{5,3,7,2,4,6,8},3

输出

示例2

输入

{},1

输出

-1

备注:

当树是空

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

linxulu

递归调用轻轻松松

int arr[1000];
int p=0;
void ldr(struct TreeNode* proot)
 {
    if(NULL == proot) return;
    ldr(proot->left);
    arr[p++]=proot->val;
    ldr(proot->right);
 }
int KthNode(struct TreeNode* proot, int k ) 
{
    ldr(proot);
    if(k>p || k<=0)return -1;
    return arr[k-1];
}

发表于 2023-07-19 20:31:59 回复(0)

lmghzzq

void insert(struct TreeNode* root,int a[],int *x){
    if(root->left!=NULL) insert(root->left,a,x);
    a[*x]=root->val;
    (*x)++;
    if(root->right!=NULL) insert(root->right,a,x);
}


int KthNode(struct TreeNode* proot, int k ) {
    // write code here
    if(proot==NULL) return -1;
    int a[1000];
    int x=1;
    for(int i=0;i<1000;i++) a[i]=-1;
    insert(proot,a,&x);
    if(a[k]==-1) return -1;
    else return a[k];
}

发表于 2022-10-08 15:26:36 回复(0)

小小鼠人可笑可笑

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param proot TreeNode类 
 * @param k int整型 
 * @return int整型
 */
static void  find(struct TreeNode *node,int * index,int *result)
{
    if(node->left!=NULL)
    {
    find(node->left, index,result);
    }
    (*index)--;
    if((*index)==0)
    {
        *result=node->val;
    }
    if(node->right!=NULL)
    {
      find(node->right, index,result);
    }
}
int KthNode(struct TreeNode* proot, int k ) {
    // write code here
    if(proot==NULL || k<=0) return -1;
    int index =k;
    int result =-1;
    find(proot, &index,&result);
    return result;
}

发表于 2022-01-28 20:58:22 回复(0)