二叉搜索树的第K大结点

题目：

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

思路：

二叉搜索树又称二叉排序树，如果根结点存在左结点，所有左结点小于根结点，如果根结点存在右结点，则所有右结点大于左结点。
基于二叉搜索树的这个特点，可以知道，二叉搜索树的中序遍历可以得到一个从小到大的序列。然后找到序列中第K个结点即可。

注：编程过程中，注意判断K的取值，以及根结点是否为空。以及二叉搜索树的结点个数是否大于K的值。

代码：

import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        TreeNode pNode = null;
        //判断pRoot为空或者k<1时返回 null
        if(pRoot == null || k < 1) return pNode;
        ArrayList<TreeNode> list = Inoder(pRoot);
        //结点个数少于K时也返回null;
        if(list.size() < k) return pNode;
        else{
            pNode = list.get(k - 1);
        }
        return pNode;
    }
    //中序遍历函数
    public static ArrayList<TreeNode> Inoder(TreeNode pRoot){
        ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        if(pRoot == null) return result;
        result.addAll(Inoder(pRoot.left));
        result.add(pRoot);
        result.addAll(Inoder(pRoot.right));
        return result;
    }
}

最后

以上就是疯狂唇彩为你收集整理的二叉搜索树的第K大结点的全部内容，希望文章能够帮你解决二叉搜索树的第K大结点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。