首页 > 代码库 > IT公司100题-9-判断整数序列是不是二元查找树的后序遍历结果

IT公司100题-9-判断整数序列是不是二元查找树的后序遍历结果

2024-07-16 09:57:23   216人阅读

问题描述：
输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入4, 8, 6, 12, 16, 14, 10，由于这一整数序列是如下树的后序遍历结果：
 10
/     \
6      14
/  \    /   \
4   8 12    16
因此返回true。
如果输入6, 5, 8, 5, 7 ，则返回false。
 
分析：

在后续遍历得到的序列中，最后一个元素为树的根结点。根节点元素将数组分为两部分，左边都小于根节点，右边都大于根节点。递归的确认左右是否是二元查找树即可。

代码实现：

 1 // 9.cc 2 #include <iostream> 3 using namespace std; 4  5 bool verify(int* a, int size) { 6     if (NULL == a || size <= 0) 7         return false; 8  9     int root = a[size - 1];10 11     // 左侧节点比根节点小12     int i = 0;13     while (i < size - 1 && a[i] <= root)14         i++;15 16     // 右侧节点比根节点大17     for(int j = i; j < size - 1; j++) {18         if(a[j] < root)19             return false;20     }21 22     // 分别验证左右子树23     bool left = true;24     if(i > 0)25         left = verify(a, i);26 27     bool right = true;28     if(i < size - 1)29         right = verify(a + i, size - i - 1);30 31     return (left && right);32 }33 34 int main() {35     int a[] = {4, 8, 6, 12, 16, 14, 10};36     int size = sizeof(a) / sizeof(int);37     bool flag = verify(a, size);38     cout << flag << endl;39     return 0;40 }

 


联系
我们