11.二叉搜索树第k个结点

目录介绍

  • 01.题目要求
  • 02.问题分析
  • 03.实例代码

好消息

  • 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.题目要求

  • 问题如下所示：
    • 给定一棵二叉搜索树，请找出其中的第k大的结点。
  • 示例 :

02.问题分析

  • 如果按照中序遍历的顺序遍历一棵二叉搜索树，遍历序列的数值是递增排序的。
  • 只需要用中序遍历算法遍历一棵二叉搜索树，就很容易找出它的第k大结点。

03.实例代码

  • 如下所示
public class Test {
    private static class BinaryTreeNode {
        private int val;
        private BinaryTreeNode left;
        private BinaryTreeNode right;

        public BinaryTreeNode() {
        }

        public BinaryTreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public static BinaryTreeNode kthNode(BinaryTreeNode root, int k) {
        if (root == null || k < 1) {
            return null;
        }

        int[] tmp = {k};
        return kthNodeCore(root, tmp);
    }

    private static BinaryTreeNode kthNodeCore(BinaryTreeNode root, int[] k) {
        BinaryTreeNode result = null;

        // 先成左子树中找
        if (root.left != null) {
          result =  kthNodeCore(root.left, k);
        }

        // 如果在左子树中没有找到
        if (result == null) {
            // 说明当前的根结点是所要找的结点
            if(k[0] == 1) {
                result = root;
            } else {
                // 当前的根结点不是要找的结点，但是已经找过了，所以计数器减一
                k[0]--;
            }
        }

        // 根结点以及根结点的左子树都没有找到，则找其右子树
        if (result == null && root.right != null) {
            result = kthNodeCore(root.right, k);
        }

        return result;
    }
}

其他内容

01.关于博客汇总链接

02.关于我的博客

  • 我的个人站点：
  • github：https://github.com/yangchong211
  • 知乎：https://www.zhihu.com/people/yczbj/activities
  • 简书：http://www.jianshu.com/u/b7b2c6ed9284
  • csdn：http://my.csdn.net/m0_37700275
  • 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
  • 开源中国：https://my.oschina.net/zbj1618/blog
  • 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
  • 邮箱：yangchong211@163.com
  • 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
  • segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
  • 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e
贡献者: yangchong211