第 33 题：二叉搜索树的后序遍历序列（递归、分治）
传送门：二叉搜索树的后序遍历序列，牛客网 online judge 地址。
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回 true，否则返回 false。
假设输入的数组的任意两个数字都互不相同。
样例：
输入：
[4, 8, 6, 12, 16, 14, 10]输出：
true
分析：前提：数组中的数字各不相同。注意到题目中已经注明了：假设输入的数组的任意两个数字都互不相同。
- 根结点是后序遍历的最后一个元素，因此一定位于给定数组的最后一位；
- 那么给定数组的最后一位就可以把这个数组分为两个部分，前半部分严格小于最后一个数，后半部分严格大于最后一个数；
根据以上两条就很容易写出递归的代码。
依据：后序遍历最后遍历到的一定是根结点。
注意：边界条件。
思想：分治。
Python 代码：
class Solution:
def verifySquenceOfBST(self, sequence):
"""
:type sequence: List[int]
:rtype: bool
"""
# 先写特殊情况
l = len(sequence)
if l == 0:
return False
if l == 1:
return True
return self.__helper(sequence, 0, l - 1)
def __helper(self, sequence, left, right):
# 先写递归终止条件
if left >= right:
return True
# 此时区间最右边的数作为标定元素
pivot = sequence[right]
# 设置一个遍历指针，把 [left, right -1] 这个区间里的元素全部看一遍
# 正确的情况是：最右边的元素把前面的数组分成两部分：
# 第 1 部分的元素全部严格小于最右边的元素
# 第 2 部分的元素全部严格大于最右边的元素
point = left
while sequence[point] < pivot:
point += 1
# 此时 [left, point - 1] 中的元素都严格比最右边的元素小
# 下面就依次验证后面的元素是不是都严格比最右边的元素大就好了
mid = point - 1
# 此后，所有的数都应该比 pivot 大
while point < right:
if sequence[point] > pivot:
point += 1
else:
return False
return self.__helper(sequence, left, mid) and self.__helper(sequence, mid + 1, right - 1)
Python 代码：分治法
class Solution:
def verifySquenceOfBST(self, sequence):
"""
:type sequence: List[int]
:rtype: bool
"""
if not sequence: return False
root = sequence[-1]
for i in range(len(sequence)):
if sequence[i] > root:
break
for j in range(i,len(sequence)):
if sequence[j] < root:
return False
left = True
if i > 0:
left = self.verifySquenceOfBST(sequence[:i])
right = True
if i < len(sequence)-1:
right = self.verifySquenceOfBST(sequence[i:-1])
if left and right: return True
return False
Java 代码：
- 根结点是后序遍历的最后一个元素，因此一定位于给定数组的最后一位。
- 那么给定数组的最后一位就可以把这个数组分为两个部分，前半部分小于最后一个数，后半部分大于最后一个数。
- 根据以上两条就很容易写出递归的代码。
Java 代码：
public class Solution {
public boolean VerifySquenceOfBST(int[] sequence) {
int len = sequence.length;
if (len == 0) {
return false;
}
if (len == 1) {
return true;
}
int l = 0;
int r = len - 1;
while (l <= r) {
int mid = judgeBST(sequence, l, r);
if (mid == -1) {
return false;
}
// 注意考虑数组下标越界的问题
// return (mid > 1 ? judgeBST(sequence, l, mid - 1) != -1 : true) && judgeBST(sequence, mid, r) != -1;
return (mid <= 1 || judgeBST(sequence, l, mid - 1) != -1) && judgeBST(sequence, mid, r) != -1;
}
return true;
}
// mid 以及 mid 以后的数子都小于 arr[r]
private int judgeBST(int[] arr, int l, int r) {
int p = arr[r];
int i = l;
int mid;
// 5，4，3，2，1
while (arr[i] < p) {
i++;
}
mid = i;
while (arr[i] > p && i < r) {
i++;
}
// 如果遍历到末尾了，就说明，在这一层，是可以构成 BST 的
if (i == r) {
return mid;
}
return -1;
}
public static void main(String[] args) {
// int[] nums1 = {5, 7, 6, 9, 11, 10, 8};
int[] nums = {5, 4, 3, 2, 1};
Solution solution = new Solution();
boolean verifySquenceOfBST = solution.VerifySquenceOfBST(nums);
System.out.println(verifySquenceOfBST);
}
}
