【剑指Offer】62、二叉搜索树的第k个结点

题目描述：

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

解题思路：

本题实际上比较简单，主要还是考察对树的遍历的理解，只要熟练掌握了树的三种遍历方式及其特点，解决本题并不复杂，很明显本题是对中序遍历的应用。

对于本题，我们首先可以知道二叉搜索树的特点：左结点的值<根结点的值<右结点的值。因此，我们不难得到如下结论：如果按照中序遍历的顺序对一棵二叉搜索树进行遍历，那么得到的遍历序列就是递增排序的。因此，只要用中序遍历的顺序遍历一棵二叉搜索树，就很容易找出它的第k大结点。

举例：

![](https://img2018.cnblogs.com/blog/1608161/201905/1608161-20190521112055125-1702218086.png)

编程实现（Java）：

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

public class Solution {

    private int num;

    TreeNode KthNode(TreeNode pRoot, int k){

        //思路：二叉搜索树中序遍历正好就是递增序列

        if(pRoot==null||k<1)

            return null;

        num=k;

       return findKthNode(pRoot);

    }

    TreeNode findKthNode(TreeNode pRoot){

        TreeNode res=null;

        if(pRoot.left!=null)

            res=findKthNode(pRoot.left);

        if(res==null){

            if(num==1)

                res=pRoot;

            --num;

        }

        if(res==null && pRoot.right!=null) //左边和根都没找到

            res=findKthNode(pRoot.right);

        return res;

    }

}

巴特西

【剑指Offer】62、二叉搜索树的第k个结点

最新文章

热门文章