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

题目描述

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

解题思路

因为二叉搜索树按照中序遍历的顺序打印出来就是排好序的,所以,我们按照中序遍历找到第k个结点就是题目所求的结点。

参考代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    int index = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot != null){
            TreeNode node = KthNode(pRoot.left, k);
            if(node != null)
                return node;
            index ++;
            if(index == k)
                return pRoot;
            node = KthNode(pRoot.right, k);
            if(node != null)
                return node;
        }
        return null;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 把二叉树打印成多行

就是二叉树的层序遍历,用队列来实现。我们需要两个变量,一个start记录当前层已经打印的节点个数,一个end记录前当层所有的节点个数,当 start == en...

1393
来自专栏desperate633

LeetCode 94. Binary Tree Inorder Traversal题目代码

643
来自专栏电光石火

java获取当前时间和前一天日期

String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

2818
来自专栏计算机视觉与深度学习基础

Leetcode 101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric arou...

17810
来自专栏赵俊的Java专栏

二叉树的所有路径

1762
来自专栏电光石火

java获取当前时间和前一天日期

String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

5945
来自专栏desperate633

LintCode 前序遍历和中序遍历树构造二叉树题目代码

802
来自专栏猿人谷

二叉树的非递归遍历(递归和非递归)

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义,...

19910
来自专栏书山有路勤为径

二叉查找树编码与解码

LeetCode 449 给定一个二叉查找树,实现对该二叉查找树编码与解码功能。编码即将二叉查找树转为字符串,解码即将字符串转为二叉查找树。不限制使用何种编码...

641
来自专栏赵俊的Java专栏

镜像二叉树

1643

扫码关注云+社区

领取腾讯云代金券