二叉搜索树的第K个节点

题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 下图二叉树中，按结点数值大小顺序第三个结点的值为4。

image

我们直到二叉搜索树的定义为：

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

根据定义可知，二叉树的中序遍历结果便是二叉搜索树的从小到大排列，中序遍历的第k个节点的值便是第k大的值。

public class Solution {
    TreeNode res = null;
    int index = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot != null) {
            KthNode(pRoot.left, k);
            index++;
            if(index == k) {
                res = pRoot;
            }
            KthNode(pRoot.right, k);
        }
        return res;
    }
}