判断整数序列是不是二叉搜索树的后序遍历结果比如,给你一个数组: inta[] = [1, 6, 4, 3, 5] ,则F(a) => false
先分析一下:
在后续遍历得到的序列中,最后一个元素为树的根结点。
从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;
从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。
根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查找树。
由于不能使用动态数组,所以我们每次递归都使用同一个数组arr,通过start和length来模拟“部分”数组。
看实现:
public static bool VerifyArrayOfBST(int[]arr, int start, int length)
{
if (arr == null || arr.Length == 0 || arr.Length == 1)
{
return false;
}
int root = arr[length + start - 1];
int i = start;
for (; i < length - 1; i++)
{
if (arr[i] >= root)
break;
}
int j = i;
for (; j < length - 1; j++)
{
if (arr[j] < root)
return false;
}
bool left = true;
if (i > start)
{
left = VerifyArrayOfBST(arr, start, i - start);
}
bool right = true;
if (j > i)
{
right = VerifyArrayOfBST(arr, i, j - i + 1);
}
return left && right;
}