专栏首页AI那点小事剑指offer——二叉搜索树的第k个结点

剑指offer——二叉搜索树的第k个结点

概述

题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。


C++ AC代码

#include <iostream>
using namespace std;


struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Solution {
    private:
        int cnt;
        TreeNode* ans;
    public:
        void Inorder(TreeNode* root){
            if(cnt == 0){
                return;
            }
            if(!root){
                return;
            }
            this->Inorder(root->left);
            cnt--;
            if(cnt != 0){
                ans = root;
            }
            this->Inorder(root->right);
        }

        TreeNode* KthNode(TreeNode* pRoot, int k){
            if(!pRoot || k < 1){
                return NULL;
            }
            cnt = k;
            ans = NULL;
            this->Inorder(pRoot);
            return ans;
        }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CCF考试——201604-3路径解析

      在操作系统中,数据通常以文件的形式存储在文件系统中。文件系统一般采用层次化的组织形式,由目录(或者文件夹)和文件构成,形成一棵树的形状。文件有内容,用于存储...

    AI那点小事
  • 开门人和关门人

    题目描述 每天第一个到机房的人要把门打开,最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录,请根据记录找出当天开门和关门的人。 输入...

    AI那点小事
  • 剑指offer——丑数

    题目描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑...

    AI那点小事
  • Windows PowerShell 实战指南-动手实验-11.7

    使用Get-Service是否可以显示一个自动启动类型且当前没有在运行的服务列表?只需回答是否可以即可。

    BigYoung小站
  • 云架构师进阶攻略

    第一个是IT架构,其实就是计算,网络,存储。这是云架构师的基本功,也是最传统的云架构师应该首先掌握的部分,良好设计的IT架构,可以降低CAPEX和OPEX,减轻...

    赵成
  • 侦听局域网内密码

    只需在前面的网络嗅探程序基础上,添加对搜索出的端口号进行的增加功能即可: 代码如下: 在DecodeIPPacket中添加: switch(::ntohs(pT...

    用户1154259
  • pytho字典集合

    字典是在大括号里放置逗号分隔的 关键字:值对 ,{key ,value},是无序的,关键字相当于一个内存地址。dictionary是python唯一的映射关系,...

    东风冷雪
  • Ubuntu 18.04 网卡配置

    其网卡配置文件为:/etc/netplan/50-cloud-init.yaml,,netplan 描述文件采用了 yaml 语法,默认是用dhcp方式,如果要...

    大大大黑白格子
  • IBASE text component

    在UI上创建一个新的IBASE,及一个新的text component,点击save button:

    Jerry Wang
  • 函数和参数

    Python里面有很多内置函数,使用函数可以让我们更快捷得实现要求,但函数那么多,死记硬背肯定不行,就需要我们平时多留心,遇到新的内置函数,多用help指令看看...

    stormwen

扫码关注云+社区

领取腾讯云代金券