二叉搜索树的后续遍历
题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路：
- 根据后续遍历的特点，每次遍历到根结点的时候都是最后一位
- 而二叉搜索树的特点就是左子树都小于等于root，右子树都大于等于root
- 所以，先找到根结点，然后由前向后遍历该序列
- 开始的部分的数值应该都是小于等于root的（左子树），当某个结点大于root的值的时候，此结点开始就是右子树
- 遍历右子树的所有数值（后序遍历的中后段），如果有数值小于root，则说明该序列不是后续遍历序列
- 递归地判断做子树和右子树，如果左右子树也都是满足后续遍历的特点，那么整个序列就都满足后续遍历的特点。
代码：
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.empty()) {
return false;
}
int length = sequence.size();
int root = sequence[length - 1];
// 从前向后遍历sequence序列
int i = 0;
for (; i < length - 1; ++i) {
if (sequence[i] > root)
break;
}
// 用另外一个变量来记录右子树开始的地方
int j = i;
// 遍历右子树，如果右子树中有元素小于root，则返回false
for (; j < length - 1; j++) {
if (sequence[j] < root) {
return false;
}
}
bool left = true;
bool right = true;
vector<int> leftSeq, rightSeq;
for (int count = 0; count < i; ++count) {
leftSeq.push_back(sequence[count]);
}
for (int count = i; count < length - 1; ++count) {
rightSeq.push_back(sequence[count]);
}
// 如果左子树不是空树，即左子树的结尾结点大于0
// 递归验证左半子树
if (i > 0) {
left = VerifySquenceOfBST(leftSeq);
}
// 如果右子树不是空树
// 递归验证右半子树
if (i < length - 1) {
right = VerifySquenceOfBST(rightSeq);
}
return left && right;
}
};
2018.10.12
