使用 C++ 中的 BST 的先序遍历求出比根结点小的元素的数量

给定先序遍历的结果，你需要找出比根结点小的元素数量。

先序遍历中的第一个元素是 BST 的根结点。我们来看一个例子。

输入

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

输出

3

比根结点小的元素有三个，根结点是 5。

算法

  • 初始化数组中的先序结果。

  • 存储第一个元素，即 BST 的根结点，到某个变量中。

  • 编写一个循环从先序结果的第二个元素开始迭代。

    • 将每个元素与根结点进行比较。

    • 如果当前元素大于根结点，则增加计数。

  • 返回计数。

实现

以下是该算法在 C++ 中的实现

#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n) {
   if (n < 0) {
      return 0;
   }
   int i, root = arr[0], count = 0;
   for(i = 1; i < n; i++) {
      if(arr[i] < root) {
         count += 1;
      }
   }
   return count;
}
int main() {
   int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
   int n = 8;
   cout << getElementsCount(preorder, n) << endl;
   return 0;
}

输出

如果你运行上面的代码，你将得到以下结果。

3

更新于： 26-10-2021

71 次浏览

开启 职业生涯

完成课程后获得认证

开始
广告