正在回答
1回答
在BST中找到第k小的树是一个很经典的面试问题：）
整体大概思路是：由于BST中，根节点的左子树的所有值都小于根节点；右子树的所有值都大于根节点。所以，我们要求整棵树的第k小元素，只要看根节点的左子树有多少个元素就好了。
如果根节点的左子树包含的元素个数left_num == k - 1，那么，根节点就是第k个元素！
如果根节点的左子树包含的元素个数left_num < k - 1，那么，整棵树的第k小元素在根节点的左子树中，我们继续找根节点的左子树的第k小元素就好了。
如果根节点的左子树包含的元素个数left_num > k - 1，那么，整棵树的第k小元素在根节点的右子树中，我们继续找根节点的右子树的第k - left_num - 1小元素就好了，这个数字是我们排除到了左子树的元素个数以及根节点：）
代码如下：（Java）
// Definition for binary tree:
// class Tree<T> {
// Tree(T x) {
// value = x;
// }
// T value;
// Tree<T> left;
// Tree<T> right;
// }
// 递归计算二分搜索树t的节点个数
int num(Tree<Integer> t){
if(t == null) return 0;
return 1 + num(t.left) + num(t.right);
}
// 求二分搜索树t的第k小元素
int kthSmallestInBST(Tree<Integer> t, int k) {
// 计算t的左子树节点个数
int left = num(t.left);
// 如果左子树节点个数 + 1(根节点)就是k，当前根节点就是结果
if(k == left + 1)
return t.value;
// 如果 k <= left，则继续在t的左子树寻找第k小元素
if(k <= left)
return kthSmallestInBST(t.left, k);
// 否则，在t的右子树寻找第k - left - 1小元素
return kthSmallestInBST(t.right, k - left - 1);
}在上面的代码中，我们使用了一个子过程来计算一棵树的节点个数。但是，可以再建树的过程中，在Node里存储一个size，用于记录以当前Node为根节点的树的节点总数，并且在添加新节点或者删除节点的时候，对size进行维护。这样做，在计算第k小节点的时候，就不需要重复计算一棵树的节点总数了。可以试试看：）
上面的代码是获得第k小的节点。如果要想获得前k个节点，整体思路也是一致的，具体实现上要有一些小改动，有兴趣也可以试试看：）
加油！：）
0
有任何疑惑可以回复我~
相似问题
登录后可查看更多问答，登录/注册
