題目描述
給定一顆二叉搜索樹圈盔，請(qǐng)找出其中的第k大的結(jié)點(diǎn)授瘦。例如二拐， 下圖二叉樹中茂翔，按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4驰吓。
image
我們直到二叉搜索樹的定義為：
二叉查找樹（Binary Search Tree）揍魂，（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹棚瘟，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空现斋，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空偎蘸，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值庄蹋； 它的左瞬内、右子樹也分別為二叉排序樹。
根據(jù)定義可知限书，二叉樹的中序遍歷結(jié)果便是二叉搜索樹的從小到大排列虫蝶，中序遍歷的第k個(gè)節(jié)點(diǎn)的值便是第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;
}
}
