二叉搜索树遍历问题

Question

bobo老师，您好！刚买了您这门课，我想请教一下如何用BST实现从数组中获取前K个最小数，我想了很久一直没有思路😂，感谢！

Answer 1

liuyubobobo 2018-10-25 04:45:22

在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）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// 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个节点，整体思路也是一致的，具体实现上要有一些小改动，有兴趣也可以试试看：）

加油！：）

• 提问者 MMXDH #1

  了解，但当原数组含有重复的几个比较小的数时，如[1，3，1，4]，BST里并不包含相同的节点，那就取不出两个1，可以这么理解吗？

• liuyubobobo 回复 提问者 MMXDH #2

  你可以让自己的BST可以接受相同节点，也可以用BSTMap的方式，每个节点记录只是多少，以及这个值在数组中有多少个。逻辑会复杂一些，但是整体思路依然可以做：）

• 提问者 MMXDH #3

  非常感谢！