剑指offer-二叉搜索树的第k个结点

题目描述

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

思路

二叉搜索树的中序遍历是非降序排序的。

因此可以考虑做中序遍历，然后遍历一个结点k–，当k为0时，就找到了第k个结点

code

int kk = 0;
TreeNode res = null;

void mid(TreeNode pRoot)
{
    // 中序遍历
    if(pRoot==null) {
        return;
    }
    mid(pRoot.left);
    kk--;
    if(kk == 0) {
        res =  pRoot;
    }
    mid(pRoot.right);
}

TreeNode KthNode(TreeNode pRoot, int k)
{
    kk = k;
    mid(pRoot);
    return res;
}