美文网首页
剑指offer06

剑指offer06

作者: MonarchNie | 来源:发表于2019-07-08 11:22 被阅读0次

题目描述

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

解题思路分析

其实要解这道题首先需要了解什么是二叉搜索树,如果不知道二叉搜索树的相关性质的话,那解答这道题就很难了。话说回来,二叉搜索树其实就是一颗二叉树拥有这样的特点:所有父节点都比其左子节点大,比其右子节点小。知道这个性质之后,这道题马上就可以想出来了,只要中序遍历一遍这棵树便可以得到一个排好序的序列,然后找第k小的节点就很简单了。

代码实现

public static TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k <= 0) {
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        // 中序遍历得到该二叉搜索树的中序遍历序列
        inOrder(pRoot, list);
        if (list.size() < k) {
            return null;
        }
        return list.get(k - 1);
    }
    private static void inOrder(TreeNode pRoot, ArrayList<TreeNode> list) {
        if (pRoot == null) {
            return;
        }
        inOrder(pRoot.left, list);
        list.add(pRoot);
        inOrder(pRoot.right, list);
    }

相关文章

  • 剑指offer06

    题目描述 给定一颗二叉搜索树,请找出其中的第K小的节点。例如,(5,3,7,2,46,8)中,按节点数值大小顺序第...

  • 剑指

    遥望中原九点烟,风云直上七重天。 今朝再向江湖去,一剑流星谁比肩? 2011.10(1488)

  • 剑指

    1. 二维数组中查找 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照...

  • 全网最全剑指offer题目解答

    【剑指offer】Java版代码(完整版) 【剑指offer】1-10题 【剑指offer】11-20题 【剑指o...

  • 剑指offer

    第一题:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,...

  • 剑指BAT

    Android工作5年半了,一毕业就开始做这行。在现在这家公司工作了3年整,最近有换工作的打算,所以在猎聘...

  • 《剑指offer》

    4.调整数组顺序使奇数位于偶数前面 题目描述:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇...

  • 气剑指

    “聚气于指尖,凝其成剑,利可断金。”牢头对身边的狱卒说。 只见牢头举起的右手指尖逐渐变红,转而变白,隐隐发出音量很...

  • 剑指offer

    二维数组中查找数在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到...

  • 剑指苍穹

    逆天命,斩苍穹,吾乃修士,率性而为!《剑指苍穹》是一款逍遥仙侠MMORPG——群魔阻道,斩群魔;妖邪拦路,诛妖邪,...

网友评论

      本文标题:剑指offer06

      本文链接:https://www.haomeiwen.com/subject/buqohctx.html