本文共 932 字，大约阅读时间需要 3 分钟。

题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。

分析

对二叉搜索树进行中序遍历，则遍历序列是递增排序的，因此中序遍历一颗二叉搜索树，可以很容易的得到它的第k大的节点。使用一个计数器变量，每遍历一个节点，计数器加1，当计数器的值等于k时，root节点即为所求节点。

/*public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {
       int count = 0;  // 遍历计数    TreeNode KthNode(TreeNode pRoot, int k) {        if(pRoot == null || k <= 0)            return null;        TreeNode target = null;        if(pRoot.left != null)      // 遍历左子树            target = KthNode(pRoot.left, k);        count++;    // 计数加1        if(target == null) {            if(count == k) {    // 如果计数等于k，则找到pRoot                target = pRoot;                return target;            }        }        if(target == null && pRoot.right != null)   // 遍历右子树            target = KthNode(pRoot.right, k);        return target;    }}

参考

转载地址：http://akxgi.baihongyu.com/