判断给定序列是否为BST后序遍历序列
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
目录
一、BST
1.1 定义
BST(Binary Search Tree)二叉搜索树:
- 所有非叶子结点至多有两个孩子(二叉搜索树也属于二叉树的范畴);
- 所有结点只存储一个关键字;
- 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;并且左右子树也是BST。(如果出现等于的情况,放在左子树部分和放在右子树部分,不影响)。
1.2 性质
- 搜索时,从根结点开始,如果查询的关键字与根结点的关键字相等,那么就命中;如果查询的关键字比结点关键字小,就进入左子树部分进行查找;否则就需要进入右子树部分进行查找。查找到最后也没能找到,则报告找不到相应的关键字。
- 如果BST的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么BST的搜索性能逼近二分查找,近似等于树高(logn);但和连续空间的二分查找相比,优点是:改变BST结构(插入或删除操作)不需要移动大段的内存数据。
- 对BST树进行中序遍历,将会得到非递减的序列。
二、思路
后序遍历BST得到的序列的性质是——最后一个元素x是根结点,以x为基准可将该序列(去掉x本身)划分成两个子序列,前一个子序列(左子树)所有元素值均小于x;后一个子序列(右子树)的所有元素值均大于x。前一个序列和后一个序列仍然满足该性质。这是一个典型的递归求解的问题!
分治法思想:字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题······直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
2.1 非递归版本
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int n = sequence.size();
int i = -1;
while(n > 1) //只有1个结点的树也是BST。
{
//第一个循环体结束时,i指向右子树序列开始位置;如果不存在右子树——会指向根结点。
while(sequence[++i] < sequence[n-1]);
//警惕数组下标越界,第二个循环体正常结束,i将指向根结点的位置
while(i < n-1 && sequence[i++] > sequence[n-1]);
if(i < n-1) return false;
i = 0;
n--;
}
return n == 0 ? false : true;
}
};
2.2 递归版本
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int n = sequence.size();
if(0 == n) return false;
return judge_impl(sequence, 0, n-1);
}
private:
bool judge_impl(vector<int>& seq, int start, int end)
{
//start为序列的起始下标,end为序列中根结点的下标(最后一个元素)
if(start >= end) return true; //只有一个结点的序列肯定符合条件
int i = start-1, j;
while(seq[++i] < seq[end]); //循环结束时i指向元素值不小于最后一个元素的位置
for(j = i; j < end-1 && seq[j] > seq[end]; ++j);
if(j < end-1) return false;
return judge_impl(seq, start, i-1) && judge_impl(seq, i, end-1);
}
};