题目:给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
思路:利用二叉树的中序遍历,遍历到第K个节点时即可。
代码:
public class Solution{
private TreeNode ret;
private int cnt = 0;
public TreeNode KthNode(TreeNode pRoot, int k) {
inOrder(pRoot, k);
return ret;
}
private void inOrder(TreeNode root, int k) {
if (root == null || cnt >= k)
return;
inOrder(root.left, k);
cnt++;
if (cnt == k)
ret = root;
inOrder(root.right, k);
}
}