专栏首页武培轩的专栏剑指Offer-二叉搜索树的第k个结点

剑指Offer-二叉搜索树的第k个结点

题目描述

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

思路

利用二叉搜索数中序遍历有序的特点。

用递归和迭代分别实现中序遍历。

代码实现

package Tree;

import java.util.Stack;

/**
 * 二叉搜索树的第k个结点
 * 给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。
 * 思路:
 * 利用二叉搜索数中序遍历有序的特点。
 */
public class Solution49 {
    private int cnt;
    private TreeNode res;

    /**
     * 迭代中序遍历
     *
     * @param pRoot
     * @param k
     * @return
     */
    TreeNode KthNode_2(TreeNode pRoot, int k) {
        if (pRoot == null || k == 0)
            return null;
        int cnt = 0;
        Stack<TreeNode> stack = new Stack<>();
        while (pRoot != null || !stack.isEmpty()) {
            while (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            pRoot = stack.pop();
            cnt++;
            if (cnt == k) return pRoot;
            pRoot = pRoot.right;
        }
        return null;
    }

    TreeNode KthNode(TreeNode pRoot, int k) {
        inOrder(pRoot, k);
        return res;
    }

    /**
     * 递归中序遍历
     *
     * @param pRoot
     * @param k
     */
    void inOrder(TreeNode pRoot, int k) {
        if (pRoot == null) return;
        if (cnt > k) return;
        inOrder(pRoot.left, k);
        cnt++;
        if (cnt == k) res = pRoot;
        inOrder(pRoot.right, k);
    }

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

        public TreeNode(int val) {
            this.val = val;

        }

    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 该如何选择消息队列?

    在高并发业务场景下,消息队列在流量削峰、解耦上有不可替代的作用。当前使用较多的消息队列有 RabbitMQ、RocketMQ、ActiveMQ、Kafka、Ze...

    武培轩
  • 该如何选择消息队列?

    在高并发业务场景下,消息队列在流量削峰、解耦上有不可替代的作用。当前使用较多的消息队列有 RabbitMQ、RocketMQ、ActiveMQ、Kafka、Ze...

    武培轩
  • 如何编写可怕的Java代码?

    我决定告诉你如何编写可怕的Java代码。如果你厌倦了所有这些美丽的设计模式和最佳实践,并且想写些疯狂的东西,请继续阅读。

    武培轩
  • MyBatis3-配置使用log4j输出日志

    配置步骤: 1、POM的依赖引入 <!-- log4j --> <!-- https://mvnrepository.com/a...

    hbbliyong
  • BigData | Apache Beam的诞生与发展

    Paper1: https://research.google.com/pubs/archive/35650.pdf

    Sam Gor
  • 比较NaN和数字

    首先要理解Python中的min函数,根据它的官方文档,有这样一句话:If multiple items are minimal, the function r...

    老齐
  • linux python 遇到的问题

    CentOS 6.5默认只安装了readline模块而没有安装readline-devel模块,所以只要安装下即可

    py3study
  • linux 正则表达式详解

    以下内容均总结自鸟哥私房菜这本书,如想详细了解,请参考该书以及其它相关资料。学习下面基础正则表达式之前请先简单了解一下grep的用法。

    我是李超人
  • 花5分钟时间来了解一下高性能网关Kong会有意外收获

    前几天开源发布了 Kong.Net 项目,收到了大量园友的反馈,开源当天就突破了 100 个star ,可喜可贺,但是从侧面也说明,我们 .NetCore 阵营...

    Edison.Ma
  • 双11请来一堆科技巨头步道“智能制造”,天猫已在为十年后的电商布局

    双11的硝烟已经弥漫在每个角落——不只是互联网,还有线下实体;不只是内地市场,还有香港台湾等境外市场;不只是促销大战,而是在产品、体验、服务和物流等维度共同发力...

    罗超频道

扫码关注云+社区

领取腾讯云代金券