二叉搜索树的第k个结点

题目描述

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

解答

中序遍历

int K,i=0;
TreeNode node = null;

TreeNode KthNode(TreeNode pRoot, int k) {
    if (k==0){
        return null;
    }
    K = k;
    dfs(pRoot);

    return node;
}

private void dfs(TreeNode pRoot) {
    if (pRoot == null) {
        return;
    }
    dfs(pRoot.left);
    if (node != null) {
        return;
    }
    if (i < K) {
        i++;
    }
    if (i == K) {
        node = pRoot;
        return;
    }
    dfs(pRoot.right);
}